Merge Sort & the n log n Lower Bound

Divide, conquer, merge

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves — using exactly the merge step you already built in Module 7's Merge Two Sorted Lists, applied to arrays instead of linked lists. It's the same move as combining two sorted stacks of paper on a desk: compare the top sheet of each stack, take the smaller one, place it face-down on a new pile, and repeat — never needing to look further into either stack than the sheet currently on top:

def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= : take LEFT on ties (stability)
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])               # attach whichever side has leftovers
    result.extend(right[j:])               # correct because both sides were pre-sorted
    return result

The cost — you already proved this

Merge sort's recurrence is T(n) = 2T(n/2) + O(n) — the exact recursion the Big O module analyzed with a level-by-level table: each of the log n levels does O(n) total merge work, giving O(n log n) overall. No new analysis needed here; recognize the shape and the answer follows from work already done.

Stability, precisely: the <= in merge means that when left[i] == right[j], the LEFT element is taken first. Since left holds elements that were originally earlier in the array, equal elements never swap relative order — merge sort is stable, unlike selection sort (which can shuffle equal elements arbitrarily during its swaps) and unlike quicksort (next lesson). Trace it on two duplicate values arriving from opposite sides — left = [2ₐ, 4], right = [2ᵦ, 3] (subscripts just for tracking, not part of the data): left[0]=2ₐ <= right[0]=2ᵦ is true, so 2ₐ is taken first; left[1]=4 compared against right[0]=2ᵦ next, 2ᵦ is smaller and taken; then 3, then 4. Result: [2ₐ, 2ᵦ, 3, 4] — 2ₐ (originally on the left, i.e. earlier in the array) stayed ahead of 2ᵦ, exactly as stability promises. Why the leftover-copying at the end doesn't break this: once one side runs out, every remaining element on the other side is provably ≥ everything already placed (both sides were sorted going in), so copying them in their existing order is not just convenient, it's the only correct choice.

Is O(n log n) actually as good as it gets? A real proof

Every comparison sort you'll meet — merge sort, quicksort, heapsort — lands at O(n log n) in the typical or worst case. That's not a coincidence to accept on faith; it's a theorem, and the proof is short enough to walk through completely.

The setup. Model ANY comparison-based sorting algorithm as a binary decision tree: each internal node is one comparison (arr[i] < arr[j]? yes/no), and each leaf represents a final determined ordering. For the algorithm to correctly sort every possible input, it must be able to distinguish all n! possible orderings of n distinct elements — if two different starting arrangements led the algorithm down the same path to the same leaf, the algorithm couldn't tell them apart, and would output the wrong order for at least one of them. So the tree needs at least n! leaves.

The bound. A binary tree of height h has at most 2^h leaves (each level at most doubles the leaf count). So:

2^h ≥ n! ⟹ h ≥ log₂(n!)

Bounding log₂(n!) without calculus. Write out the product and keep only the larger half of the factors:

n! = n · (n−1) · (n−2) ⋯ 1 ≥ n · (n−1) ⋯ (n/2) ≥ (n/2)^(n/2)

(the last n/2 factors are each at least n/2). Taking log₂ of both sides:

log₂(n!) ≥ (n/2) · log₂(n/2) = Ω(n log n)

The conclusion. The decision tree's height — which equals the WORST-CASE number of comparisons any correct comparison sort must make — is Ω(n log n). Merge sort's O(n log n) isn't a limitation of one algorithm; it's provably optimal among all algorithms that sort by comparing elements. Nothing built purely from "is A < B?" questions can do better in the worst case, ever.