Objective
Watch merge sort split the array to single elements and merge them back in sorted order, achieving its guaranteed O(n log n).
The idea
Merge sort divides until the pieces are trivial, then merges in order. Its cost never depends on the input - a fair trade for the memory it uses.
Try this
- 1Watch the array halve until each piece is one element.
- 2Follow the merge that combines two sorted halves.
- 3Run it on a nearly-sorted and a reversed array - same cost?
- 4Count total comparisons against quick sort.
Watch for
- Divide-and-conquer: split, sort, merge.
- Merging two sorted runs takes linear time.
- Cost is always O(n log n), regardless of input order.
- It needs extra memory proportional to n.