Merge sort: divide and conquer
Bubble and selection sort hit a wall: O(n²) on 10 million rows is roughly 50 trillion comparisons. Merge sort was invented (John von Neumann, 1945) to break that wall, and it still earns its keep: it is stable — 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 big for memory (sort chunks, then merge 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 is easy, you just repeatedly take the smaller front element.
The clever part is the strategy, called divide and conquer:
- Divide: split the list in half.
- Conquer: sort each half (by doing this whole procedure to it, a function calling itself, which is called recursion. Unit 5 explores recursion deeply, here you just need to trust it).
- Combine: merge the two sorted halves.
A one-element list is already sorted, so the splitting stops there. Every level of splitting halves the size, log₂(n) levels, and each level does O(n) merge work: O(n log n) total.
Code exercise · python
Run this. merge keeps one index per list, i and j, and always copies the smaller of the two front values — so the output stays sorted because every copy is the smallest thing left anywhere. This is the workhorse of merge sort.
Code exercise · python
Your turn. merge is written for you. Complete merge_sort: lists of length 0 or 1 are returned as-is, otherwise split at the middle, merge_sort each half, and merge them. The print line traces every merge, so your output shows the whole tree from the figure.
Quiz
Two sorted halves with n elements in total are merged into one list. At most how many comparisons does the merge make?
Quiz
Why is merge sort O(n log n)?