Merge sort: divide and conquer

Merge sort: divide and conquer

Bubble and selection sort hit a wall. O(n²) on 10 million rows is roughly 50 trillion comparisons, which is not a slow program but an impossible one.

Merge sort was invented by John von Neumann in 1945 to break that wall, and it still earns its keep for three reasons.

It is stable, meaning items that compare equal keep their original order, which lesson 3-4 shows is a feature users notice. It is how you sort files too large for memory, by sorting chunks and then merging them. And Python's built-in Timsort is a tuned merge sort at heart.

Merge sort is built on one modest skill, merging two already-sorted lists into one sorted list. That part is easy, since it just means repeatedly taking the smaller of the two front elements.

The clever part is the strategy, called divide and conquer.

1. Divide the list in half.
2. Conquer by sorting each half, which means running this whole procedure on it. A function calling itself is called recursion, and unit 5 explores it deeply, so for now it is enough to trust that it works.
3. Combine by merging the two sorted halves.

A one-element list is already sorted, so the splitting stops there and needs no special reasoning.

The cost follows from the shape. Every level of splitting halves the size, giving log₂(n) levels, and each level does O(n) merge work, for O(n log n) in total.

The merge step

Merging keeps one index per list and always copies the smaller of the two front values.

def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

print(merge([2, 5, 9], [1, 3, 8, 10]))

Output

[1, 2, 3, 5, 8, 9, 10]

The output stays sorted because every copy is the smallest value left anywhere. Since both inputs are sorted, the smallest remaining element must be at the front of one list or the other, so comparing two candidates is enough.

The <= rather than < is what makes merge sort stable. On a tie the element from a, the earlier list, is copied first, which preserves the original relative order.

The two extend calls handle the leftovers. The loop ends as soon as either list runs out, and whatever remains in the other is already sorted and already larger than everything copied, so it can be appended wholesale.

Only one of those two extends ever does anything, and writing both avoids a branch to work out which.

merge_sort, tracing every merge

The recursion splits, and the print shows each merge as it completes.

def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    merged = merge(left, right)
    print(f"merge {left} + {right} -> {merged}")
    return merged

print(merge_sort([5, 3, 8, 1, 9, 2]))

Output

merge [3] + [8] -> [3, 8]
merge [5] + [3, 8] -> [3, 5, 8]
merge [9] + [2] -> [2, 9]
merge [1] + [2, 9] -> [1, 2, 9]
merge [3, 5, 8] + [1, 2, 9] -> [1, 2, 3, 5, 8, 9]
[1, 2, 3, 5, 8, 9]

The base case comes first, and it is load-bearing. Without if len(nums) <= 1: return nums the function would keep splitting empty lists and call itself forever.

Slicing does the split, with nums[:mid] and nums[mid:] covering every element exactly once.

The trace reads bottom-up, which is the thing to notice about recursion. The first line printed is the deepest merge, because no merge can print until both of its recursive calls have finished.

The last line is the final merge of two sorted halves of three, and every element in the output passed through exactly one merge per level. Six elements over about three levels is why the work is n log n rather than n².

About n comparisons, or more precisely at most n − 1.

Each comparison sends exactly one element to the output, and there are n elements to move, so the comparison count cannot exceed the element count.

The last element needs no comparison at all, since by then one list is empty and the remainder is copied by extend. That is where the −1 comes from.

The important part is what this per-merge cost implies. O(n) work per level, times log₂(n) levels of splitting, is precisely where O(n log n) comes from.

It also explains why merge sort has no bad inputs. The merge cost depends on the element count rather than on their arrangement, so the worst case and the average case are the same.

Because there are log₂(n) levels of halving, and the merges on each level touch all n elements once.

Halving until pieces reach size 1 takes log₂(n) levels, which is the same halving arithmetic as binary search in lesson 2-2. For a million items that is about 20 levels.

On any single level the pieces are different sizes but they partition the whole list, so the merges on that level collectively copy every element exactly once. That is O(n) per level regardless of how the level is divided up.

Multiplying gives O(n) work × O(log n) levels = O(n log n). For a million items that is roughly 20 million steps against bubble sort's trillion.

There is also a cost merge sort pays that the O(n log n) hides. Each merge builds a new list, so it needs O(n) extra space, which is the trade against quicksort's in-place partitioning in the next lesson.