← Back to the sorting page
Merge Sort & Stable Divide-and-Conquer
Split, sort halves, merge. Guaranteed O(n log n), stable, and the only comparison sort that streams — which is why databases external-sort with it.
What to know
- Stability preserves equal elements’ order — required for multi-key sorts.
- The merge step counts inversions and "counts smaller after self" almost for free.
- External merge sort: sort chunks that fit in RAM, then k-way merge runs from disk.
- On linked lists, merge sort needs O(1) extra space — the list sort of choice.
In the wild: Database ORDER BY spills, log-file merging, MapReduce shuffle phase.
Algorithms to reach for
Merge sort
O(n log n)Stable guaranteed O(n log n)
Count inversions
O(n log n)Measure disorder during merge
External k-way merge
O(n log n)Sort data far larger than memory
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.