Merge sort and quick sort

Beating O(n²)

Simple sorts fix one inversion at a time, and a list can have about n²/2 inversions. To do better, an algorithm must move items far in one step. Both merge sort and quick sort use divide and conquer from Module 5: split the problem, solve the halves recursively, and combine. Any sort that only compares items needs about n log n comparisons in the worst case, so O(n log n) is the best a comparison sort can do.

Merge sort

Split the list in the middle, sort the left half and the right half recursively, then merge the two sorted halves with two pointers (you wrote merge in Module 5). A list of 0 or 1 items is already sorted: that is the base case.

def merge_sort(nums):
    if len(nums) <= 1:
        return list(nums)
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= takes from the left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # Output: [3, 9, 10, 27, 38, 43, 82]

There are about log₂ n levels of splitting, and each level merges n items in total, so merge sort is O(n log n) in the best, average AND worst case. The merge needs a new list, so it uses O(n) extra memory (plus O(log n) for the recursion). Because ties take from the left half first, it is stable. It also suits data too big for memory (external sorting) and linked lists, where splitting and merging need no random access.

Quick sort

Pick one item as the pivot. Partition: rearrange the list so items smaller than the pivot come before it and bigger items after it. The pivot is now in its final place. Then quick sort the left part and the right part. There is no combine step; the work happens in the partition.

import random

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    p = random.randint(lo, hi)            # random pivot
    a[p], a[hi] = a[hi], a[p]             # move it to the end
    pivot, store = a[hi], lo
    for i in range(lo, hi):               # Lomuto partition
        if a[i] < pivot:
            a[i], a[store] = a[store], a[i]
            store += 1
    a[store], a[hi] = a[hi], a[store]     # pivot to its final place
    quick_sort(a, lo, store - 1)
    quick_sort(a, store + 1, hi)
    return a

print(quick_sort([38, 27, 43, 3, 9, 82, 10]))   # Output: [3, 9, 10, 27, 38, 43, 82]

Why the pivot matters

If the pivot lands near the middle each time, the parts halve and quick sort is O(n log n). If it is always the smallest or largest item, one side is empty and the other has n − 1 items, so there are n levels: O(n²) time and O(n) recursion depth. That happens with "always take the last item" on a list that is already sorted, a very common input. Two fixes: a random pivot (bad splits become extremely unlikely on any input) or median-of-three (the middle value of the first, middle and last items). Many equal values cause the same trouble with the simple partition above; a three-way partition (less, equal, greater) fixes it.

Lomuto and Hoare partition, in words

• Lomuto: the pivot sits at the end; one pointer scans left to right and a store pointer marks where the next smaller item goes. Easy to write, but it does more swaps.
• Hoare: two pointers start at both ends and move towards each other, swapping a too-big item on the left with a too-small item on the right. Fewer swaps and better with duplicates, but the boundaries are trickier, and the pivot does not necessarily end in its final place.

Comparing them

Common mistakes

• Using < instead of <= in the merge, which takes from the right on ties and breaks stability. Fix: take from the left when equal.
• Forgetting to copy the leftovers after the merge loop. Fix: extend with left[i:] and right[j:].
• Always picking the first or last item as pivot, so sorted input becomes O(n²) and may hit the recursion limit. Fix: random or median-of-three pivot.
• Recursing on a range that includes the pivot, so the range never shrinks. Fix: recurse on lo..store − 1 and store + 1..hi.
• Claiming quick sort is "always O(n log n)". Fix: say "O(n log n) on average, O(n²) worst case".