Mergesort and Quicksort: Two Dominant Approaches for Efficient Sorting

Sorting data is one of the fundamental operations in computing, and choosing an appropriate sorting algorithm can significantly affect the performance of an application. Two of the best-known and widely used algorithms are Mergesort and Quicksort. These two approaches, both based on the “divide and conquer” principle, are capable of ordering sequences of data efficiently, but they adopt different strategies to achieve this goal.

[wpda_org_chart tree_id=44 theme_id=50]

Mergesort and Quicksort

Mergesort and Quicksort are efficient and widely used sorting algorithms. Each algorithm has its own characteristics and strengths, but both use the “divide and conquer” approach to sort a sequence of elements.

Mergesort, designed by John von Neumann and further developed by John McCarthy, is known for its stability and guaranteed time complexity. This algorithm works by splitting the sequence into two parts, sorting each part separately, and finally combining the parts into an ordered sequence. Mergesort’s stability is especially useful when you need to maintain the relative order of elements with equal keys. Mergesort’s efficiency is highlighted by its O(n log n) time complexity, making it a reliable choice for data sequences of different sizes.

Quicksort, Invented by Tony Hoare, stands out for its speed and simplicity. This algorithm works by dividing the sequence through a pivot element, placing the minor elements on the left and the major ones on the right. Subsequently, the two resulting parts are sorted separately, without the need for a combining step. The average time complexity of Quicksort is also O(n log n), making it highly efficient in practice. However, it is important to note that its worst case can result in quadratic time complexity, if the choice of pivot is not carefully managed.

Mergesort

Mergesort was invented by John von Neumann in 1945, although the modern version was developed by John McCarthy in 1956. Mergesort is known for its stability and guaranteed time complexity.

The Mergesort algorithm works as follows:

• Divide: The sequence of elements is divided into two equal parts.
• Conquest: Each part is sorted separately using the Mergesort algorithm recursively.
• Combine: The two ordered parts are merged to create an ordered sequence.

This process of dividing, sorting, and combining continues recursively until the sequence is completely sorted. Mergesort is known for its stability, which means it maintains the relative order of equally keyed elements.

The time complexity of Mergesort is , where “n” is the size of the sequence

def mergesort(arr):
    if len(arr) <= 1:
        return arr

    middle = len(arr) // 2
    left_half = mergesort(arr[:middle])
    right_half = mergesort(arr[middle:])

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example of use:
not_ordered_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
ordered_list = mergesort(not_ordered_list)
print("Mergesort:", ordered_list)

Running the code you will get the following result:

Mergesort: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Quicksort

Quicksort was invented by Tony Hoare in 1960 and is known for its speed and simplicity. It is one of the most widely used sorting algorithms and is often used in the standard libraries of many programming languages.

The Quicksort algorithm works as follows:

• Partition: An element, known as a “pivot”, is chosen from the sequence. The minor elements of the pivot are placed on the left, while the major ones are placed on the right.
• Conquer: The two resulting parts (left and right of the pivot) are neatly separated, recursively using the Quicksort algorithm.
• Combine: Since each partition is already sorted, no combining step is necessary.

This process of recursive partitioning and sorting continues until the entire sequence is sorted. Quicksort is known for its speed, especially on average, although its worst case can be in specific situations.

The average time complexity of Quicksort is , making it very efficient in practice. However, its worst case occurs when the pivot is chosen unfavorably, leading to quadratic time complexity. To mitigate this problem, modern Quicksort implementations use intelligent pivoting strategies.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        lesser = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quicksort(lesser) + [pivot] + quicksort(greater)

# Example of use:
not_ordered_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
ordered_list = quicksort(not_ordered_list)
print("Quicksort:", ordered_list)

Running the code you will get the following result:

Quicksort: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Conclusion

In summary, Mergesort and Quicksort are both efficient sorting algorithms that use the “divide and conquer” approach. Mergesort is known for its stability, while Quicksort is known for its average speed. The choice between the two often depends on the specific needs of the problem and the characteristics of the data to be sorted.