Merge Sort and Quicksort in Python: Pivot Choice and Worst Cases

Two timing gates at a race each hand you a list of finish times, already sorted. Combining them into one ranked list takes no cleverness at all: compare the two front entries, take the smaller, repeat. At most len(a) + len(b) - 1 comparisons. Merge sort is that one observation applied again and again, and it is the cleanest way to see how sorting can get below quadratic: split the list in half, sort each half, merge.

Merge sort: split, sort the halves, merge

def merge(left, right, counter):
    """Merge two sorted lists. <= keeps equal items in their original order."""
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        counter[0] += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


def merge_sort(a, counter):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid], counter), merge_sort(a[mid:], counter), counter)


# Two finish-time lists from two timing gates, each already sorted
gate_a = [61.2, 64.8, 70.1, 75.5]
gate_b = [60.9, 66.0, 66.4, 80.3]
c = [0]
print(merge(gate_a, gate_b, c), "comparisons:", c[0])

for n in (1000, 2000, 4000, 8000):
    c = [0]
    data = [(i * 7919) % n for i in range(n)]
    assert merge_sort(data, c) == sorted(data)
    print(f"n={n:5d} comparisons={c[0]:7d}")

[60.9, 61.2, 64.8, 66.0, 66.4, 70.1, 75.5, 80.3] comparisons: 7
n= 1000 comparisons=   8415
n= 2000 comparisons=  18126
n= 4000 comparisons=  38577
n= 8000 comparisons=  81534

Why n log n? Halving a list of n items takes about log2(n) levels (about 10 for 1,000 items), and the merges at each level together touch every item once, so each level costs at most n comparisons. For n = 1,000 that bound is about 9,966, and the measured 8,415 sits just under it. Doubling n slightly more than doubles the work, in sharp contrast to the quadrupling you saw in the previous lesson.

Merge sort has three properties worth remembering. Its running time barely depends on the input order, so there is no bad case to trigger. It is stable, thanks to the <= in merge. And it needs O(n) extra space for the merged output. The slicing in this version copies lists at every level, which is simple to read but wasteful; industrial versions merge through one reusable buffer.

Quicksort: partition around a pivot

Quicksort goes the other way. Instead of merging at the end, it does the hard work first: pick a pivot, rearrange the list so everything smaller is on its left and everything larger on its right, which puts the pivot in its final position, then recurse on each side. Nothing needs merging, and the work happens in place. The version below takes the pivot rule as a function so we can compare rules, and it records comparisons and the deepest recursion level.

def scrambled(n, seed=7):
    """Deterministic pseudo-random list without importing random."""
    out, x = [], seed
    for _ in range(n):
        x = (x * 1103515245 + 12345) % 2**31
        out.append(x % 1000)
    return out


def quicksort(a, pick):
    """In-place quicksort (Lomuto partition). `pick` chooses the pivot index in a[lo..hi].
    Returns (comparisons, deepest recursion level)."""
    stats = {"cmp": 0, "depth": 0}

    def sort(lo, hi, depth):
        if lo >= hi:
            return
        stats["depth"] = max(stats["depth"], depth)
        p = pick(a, lo, hi)
        a[p], a[hi] = a[hi], a[p]                  # park the pivot at the end
        pivot, store = a[hi], lo
        for i in range(lo, hi):
            stats["cmp"] += 1
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]          # pivot lands in its final slot
        sort(lo, store - 1, depth + 1)
        sort(store + 1, hi, depth + 1)

    sort(0, len(a) - 1, 1)
    return stats["cmp"], stats["depth"]


def first(a, lo, hi):
    return lo


def middle(a, lo, hi):
    return (lo + hi) // 2


def median_of_three(a, lo, hi):
    mid = (lo + hi) // 2
    trio = sorted([(a[lo], lo), (a[mid], mid), (a[hi], hi)])
    return trio[1][1]

from quicksort_lab import scrambled, quicksort, first, middle, median_of_three

n = 600
inputs = {"already sorted": list(range(n)), "reversed": list(range(n, 0, -1)), "scrambled": scrambled(n)}
print(f"n = {n}; each cell is comparisons / deepest recursion")
print(f"{'pivot rule':16}" + "".join(f"{name:>18}" for name in inputs))
for label, rule in [("first element", first), ("middle element", middle), ("median of three", median_of_three)]:
    cells = []
    for data in inputs.values():
        work = list(data)
        cmp_count, depth = quicksort(work, rule)
        assert work == sorted(data)
        cells.append(f"{cmp_count} / {depth}")
    print(f"{label:16}" + "".join(f"{c:>18}" for c in cells))

n = 600; each cell is comparisons / deepest recursion
pivot rule          already sorted          reversed         scrambled
first element         179700 / 599      179700 / 599         6344 / 19
middle element            4387 / 9         4568 / 11         6076 / 20
median of three           4387 / 9         7498 / 18         4866 / 13

What the pivot table says

The first row is the textbook worst case. Choosing the first element as pivot on sorted input means every partition splits off one item and leaves a list of n - 1, so the comparisons are 599 + 598 + ... + 1 = 179,700, exactly n(n-1)/2, and the recursion is 599 levels deep. On scrambled input the same rule needs only 6,344 comparisons at depth 19. The algorithm did not change; the pivots stopped being balanced.

The middle element handles sorted and reversed input well because the middle of an ordered list is its median. Median-of-three also does well on sorted data, yet it is worse than the middle rule on reversed data in this table (7,498 comparisons), a reminder that a pivot heuristic reduces the chance of a bad split on common patterns and guarantees nothing. Real implementations either pick the pivot at random, which makes a bad case a matter of chance rather than input shape, or add a fallback such as switching to heapsort when the recursion gets too deep.

Depth matters in Python for a second reason. Each recursive call uses a stack frame and CPython's default limit is around a thousand frames. A first-pivot quicksort on 2,000 sorted items does not just run slowly; it crashes.

from quicksort_lab import quicksort, first

data = list(range(2000))              # already sorted, first element as pivot
try:
    quicksort(data, first)
except RecursionError as err:
    print("RecursionError:", err)

RecursionError: maximum recursion depth exceeded

Common mistakes

• Always taking the first or last element as pivot. Symptom: fast on random test data, then a timeout or RecursionError: maximum recursion depth exceeded the day someone passes already-sorted input.
• Using `<` instead of `<=` in the merge step. Symptom: records with equal keys come out in swapped order, so a merge sort that should be stable is not.
• A wrong base case. Symptom: RecursionError from a merge sort that never reaches lists of length 0 or 1, usually because the split does not shrink the list.
• Off-by-one in the partition boundaries. Symptom: items missing or duplicated in the output, or IndexError: list index out of range. Always assert result == sorted(data) in a test harness, as the snippets do.
• Rewriting these in production Python. Symptom: slower and less reliable than sorted(), which is implemented in C and already stable. Write them to learn, not to ship.

How this shows up in real projects and interviews

Divide and conquer is a pattern bigger than sorting: merging sorted files, counting inversions with a modified merge, and external sorting of data that does not fit in memory are all merge sort in disguise, and quickselect (finding the k-th smallest) is quicksort that recurses into one side. Interviewers expect you to write either sort, state average and worst-case costs, and explain the pivot problem, usually followed by "how would you avoid the worst case?" (random pivot, median-of-three, three-way partition, depth-limited fallback). Mention stability and memory when asked to compare the two. Both sorts reappear when you reason about the O(n) alternatives in the next lesson, and recursion depth links back to the call-stack discussion in Data Structures.