Card 08/ 08
Recap: Merge Sort
Split, sort, merge with <=, and the same O(n log n) whatever the input.
Merge sort comes down to the seven ideas below, each listed with the card that covers it. One operation holds them together: the merge, which turns two sorted runs into one by looking only at their fronts, and which every other idea here either performs, protects or costs.
| The idea | Where |
|---|---|
| Split at the middle without comparing, down to single items; merge sorted halves back up | Merge Sort: Split in Half, Sort Each Half, Merge |
| Merge with two indices, take the smaller front, copy the rest when one half runs out | Merge Two Sorted Halves |
| Compare with <= so a tie takes the left item and the sort stays stable | Taking From the Right Half on a Tie |
| Allocate one buffer and pass half-open ranges, rather than a new array per merge | Merge Sort in Python, Java and TypeScript |
| Every level merges all n items over log₂ n levels, so no input is faster or slower | Why Merge Sort Costs the Same on Every Input |
| A linked list is split by counting and merged by relinking, with no buffer | Merge Sort Example: Sorting a Linked List |
| The merge works on any two ordered lists, and which list goes first decides the ties | Practice: Merging Two Sorted Departure Boards |
The figures to keep are these.
- Time, every case
- O(n log n)
- n log₂ n items merged on any input
- Comparisons
- About n log₂ n / 2 to n log₂ n
- fewest on sorted or reversed input
- Extra space, array
- O(n)
- one buffer, plus an O(log n) stack
- Extra space, linked list
- O(log n)
- the stack only; nodes are relinked
- Stable
- Yes
- with <= in the merge
- In place
- No
- on an array
Together they let you trace merge sort's splits and merges on a small array, write a merge that keeps equal keys in their input order and loses no items, and state its time and space in every case.
← → move through sections and cards