Merge sort

Split in half, sort each half, merge. The first O(n log n) sort — no bad case.

The merge is the trick

Two sorted runs → one sorted run in O(n) (two fingers, take the smaller)
Do that at every level of a halving split
log n levels × O(n) per level = O(n log n)
Stable (ties go left); needs O(n) scratch memory

Watch runs merge and grow

12 runs of length 1 → 2 → 4 → 8 → sorted. Each green run is one merge.

O(n log n), guaranteed

T(n) = 2T(n/2) + O(n) = O(n \log n)

No adversarial input — the split doesn't depend on the data.

The trade

Merge sort: guaranteed O(n log n), stable, sequential — but O(n) memory
Best for: unpredictable input, external data, linked lists
vs. quicksort (next): in-place, faster, but O(n²) worst case

Takeaway

Trade memory for a guarantee. The sort behind every stable library sort and every sort-a-file-too-big-for-memory. Next: quicksort.

1 / 6