Merge Sort
Scenario
You have two stacks of exam papers, each already sorted by score. You need one combined sorted pile.
Do you re-sort all of them from scratch — or is there a way to merge the two sorted piles in a single pass?
Why it exists
Problem: Sorting n items by comparing and swapping neighbours (bubble, insertion, selection) costs O(n^2) — on a million items that's a trillion operations, far too slow.
Naive approach: Quadratic sorts repeatedly walk the array swapping out-of-order neighbours; the number of comparisons grows with the square of the input.
Better idea: Split the array in half, sort each half independently, then MERGE the two sorted halves in one linear pass. Splitting gives only log n levels, and each level does O(n) work — so the whole thing is O(n log n).
Mental model
Keep splitting until each piece is a single element (already sorted), then zip the sorted pieces back together two at a time.
The split phase is trivial — halve, halve, halve until size 1. The real work is the merge: given two already-sorted lists, walk a finger down each and repeatedly take the smaller front element. Because both inputs are sorted, you never look back — one linear sweep produces a sorted combination. Merging bubbles correctness up the recursion tree: single elements are sorted by definition, and every merge preserves sortedness for a larger range.
Repeated decision: At each merge step: which of the two current front elements (left vs right) is smaller? Take that one and advance its finger.
Explanation
Merge sort has two phases: SPLIT and MERGE. The split phase is almost free — you keep halving the range until every piece holds a single element. A single element is, by definition, already sorted. That is the base case the recursion bottoms out on.
All the real work happens on the way back up, in the merge. Suppose you have two halves that are each already sorted. Put a finger at the start of each. Compare the two elements under your fingers, take the smaller one, write it to the output, and advance that finger. Repeat. Because both halves are sorted, the smaller of the two current fronts is always the smallest element you have not yet placed — so one straight left-to-right sweep, O(n), produces a fully sorted combination. When one half runs out, you copy the rest of the other half over (it is already sorted).
Now stack these merges up the recursion tree. Pairs of single elements merge into sorted pairs; pairs of sorted pairs merge into sorted runs of four; and so on, doubling the sorted-run size each level until the whole array is one sorted run. There are log2(n) levels because you halved on the way down, and each level merges n elements in total — so the cost is n × log n. Crucially, this is true no matter how the input was arranged: merge sort has no bad-input case, which is exactly what quicksort cannot promise.
The one cost is space: the merge needs somewhere to write the combined result, so a standard implementation uses an O(n) scratch array. That is the trade you make for a guaranteed O(n log n), stable sort.
Key points
- Complexity: O(n log n) time in all cases (best/average/worst), O(n) auxiliary space. There are log2(n) levels of splitting and each level merges a total of n elements.
- The merge invariant: Merging two SORTED lists works only because the smaller front element is guaranteed to be the next element overall — that's what makes it a single O(n) pass, not a re-sort.
- Stable, not in-place: Equal elements keep their original order (stable), but a standard merge needs an O(n) scratch array — it is not in-place.
Pattern: Divide & Conquer
Recognition cues:
- The problem splits into independent subproblems of the same shape.
- Subproblem results combine cheaply (here, an O(n) merge).
- You can write a recurrence like T(n) = 2T(n/2) + O(n).
Failure signals
- An O(n^2) sort is too slow for the input size (n is large, or the array is nearly reverse-sorted).
- You need a STABLE sort with guaranteed O(n log n) regardless of input order.
- The data is too big for RAM and must be sorted in streamed, pre-sorted runs.
Engineering examples
External sorting in databases
Sorting a dataset far larger than memory.
Merge naturally combines sorted runs streamed from disk — external merge sort is the backbone of sorting in database engines.
Standard library sorts
Sort records without reordering equal keys.
Timsort (Python's and Java's default) is a merge-sort hybrid — it exploits already-sorted runs and is stable.
When not to use
- Small or nearly-sorted arrays: Insertion sort has lower overhead and better cache behaviour; that's why Timsort switches to it on small runs.
- Memory-constrained, must sort in place: Standard merge sort needs O(n) extra space; prefer heapsort or quicksort when auxiliary memory is precious.
Common mistakes
- Thinking merge sort is in-place: The merge step writes into an O(n) auxiliary buffer. If an interviewer asks for O(1) extra space, merge sort (in its standard form) is the wrong answer.
- Off-by-one in the merge bounds: Mishandling the midpoint or the leftover 'tail' of one half is the classic bug. After the main compare loop, you must drain whichever half still has elements.
- Re-sorting instead of merging: The whole speedup comes from the two halves already being sorted. If you sort during the merge, you've thrown away the O(n) guarantee and made it O(n log^2 n) or worse.
Glossary
- base case
- The condition that stops a recursive function from calling itself forever.
- recursion tree
- A visual way to trace recursive calls branching out, showing how the problem is broken down.
- in-place
- An algorithm that modifies the original array without needing extra memory proportional to the input size.
- stable
- A sorting algorithm that preserves the original relative order of equal elements.
- auxiliary space
- The extra memory an algorithm needs to do its work, not counting the memory taken by the input itself.
Recall questions
- Why is merge sort O(n log n)?
- What invariant makes the merge step a single linear pass?
- Is merge sort stable? Is it in-place?
- When would you choose merge sort over quicksort?
Questions & answers
Why is merge sort O(n log n) but quicksort can degrade to O(n^2)?
Merge sort always splits exactly in half (balanced recursion → log n depth); quicksort's split depends on the pivot and can be lopsided, giving O(n) depth in the worst case.
Approach: Tie the complexity directly to the balance of the recursion tree.
Merge two sorted linked lists into one sorted list.
Walk both lists with two pointers, repeatedly splicing the smaller head into the result; append the remaining tail. O(n + m), O(1) extra.
Approach: Recognize this IS the merge step of merge sort, isolated.
Count the number of inversions in an array.
Run merge sort and, during each merge, count how many left-half elements are greater than the right-half element being placed. O(n log n).
Approach: Pattern transfer: the merge step can do useful counting work for free.
Interesting facts
- Merge sort was invented by John von Neumann in 1945 — one of the first algorithms designed for a stored-program computer.
- Quicksort is O(n^2) in the worst case yet often beats merge sort in practice, because it sorts in place and has better cache locality — a reminder that Big-O isn't the whole story.
Continue learning
Previous: The call stack
Previous: Recursion tree
Related: Merge two sorted lists
Related: Binary Search
Related: Recursion tree