Merge Sort
Split in half, sort each side, merge two sorted streams — guaranteed O(n log n), stable, and built for data that doesn't fit in memory.
Hands on Interactive visualization
Implementation Code
export function mergeSort(a: number[]): number[] {
if (a.length <= 1) return a;
const mid = a.length >> 1;
const left = mergeSort(a.slice(0, mid));
const right = mergeSort(a.slice(mid));
const out: number[] = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
// <= takes from the left run on ties — this is what makes it stable.
out.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
while (i < left.length) out.push(left[i++]);
while (j < right.length) out.push(right[j++]);
return out;
}Big-O Complexity
The O(n) auxiliary buffer is the price of stability at guaranteed O(n log n); truly in-place stable merging exists but is impractical.
In production When to use
External merge sort is the standard way databases sort data larger than RAM: sort chunks that fit in memory, spill sorted runs to disk, then k-way merge. Index builds and ORDER BY spills work this way in PostgreSQL and most engines.
Stable sorts in standard libraries are merge-based: Java's Arrays.sort for objects and Python's sorted() use TimSort, a merge sort refined with run detection; Rust's stable sort is also merge-based.
The shuffle-and-sort phase of MapReduce-style systems is a distributed merge sort: each node produces sorted runs that are merged across the cluster.
Merge sort is the natural O(n log n) sort for linked lists — merging relinks nodes with O(1) extra space and no random access, where quicksort's index arithmetic is useless.
Stability lets you sort by secondary key first, then primary — equal primaries keep the secondary order. Essential for report generation and spreadsheet-style column sorting.
The two halves are completely independent, so merge sort parallelizes cleanly: fork the halves, join with a merge. Parallel merge-based sorts are common in multicore runtimes.
Trade-offs Strengths & weaknesses
- Guaranteed O(n log n) — no adversarial input can degrade it.
- Stable: the backbone of every stable stdlib sort.
- Sequential access pattern: ideal for disk, tape, SSD streaming, and linked lists.
- Trivially parallelizable — halves are independent until the final merge.
- Scales beyond RAM via external sorting with k-way merges.
- Predictable performance simplifies capacity planning and latency budgets.
- O(n) auxiliary memory — a real cost for large in-memory arrays.
- Not adaptive in its textbook form: sorted input still costs O(n log n).
- Higher constant factors than quicksort on arrays due to copying between buffers.
- Cache behavior is worse than quicksort's partition-in-place access pattern.
- Allocation pressure if the auxiliary buffer is not reused across recursion.
Intuition Mental model
Merging two sorted piles of cards
Two face-up piles, each already sorted with smallest on top. Building one sorted pile from them requires only ever looking at the two top cards.
- Split the deck in half again and again until every pile is a single card — one card is trivially sorted.
- Merge piles pairwise: compare the two top cards, move the smaller one to the output pile.
- On ties, take from the left pile — that habit is exactly what makes the sort stable.
- When one pile empties, sweep the remainder of the other pile straight across.
- Each merge level touches every card once: log n levels × n cards = n log n moves.
Prep Interview questions
Why does merge sort need O(n) extra space, and can you avoid it?
How would you sort a 100 GB file with 4 GB of RAM?
Why is merge sort preferred over quicksort for linked lists?
During the merge, why must you take from the left run on ties?
How do you count inversions in an array efficiently?
Watch out Common bugs
In fixed-width integer languages, lo + hi can overflow for large arrays — the bug that sat in Java's own binarySearch for years. Use lo + (hi - lo) / 2.
Using < instead of <= when comparing left against right takes the right element on ties, reordering equal keys. Harmless for ints, wrong for records.
Allocating inside merge() turns O(n) auxiliary space into O(n log n) total allocation churn and can dominate runtime via GC or malloc pressure. Allocate once and reuse.
Mixing [lo, hi] and [lo, hi) conventions across mergeSort() and merge() drops or duplicates the boundary element. Pick half-open ranges everywhere and stay consistent.
One screen Cheat sheet
Divide in half, recurse, then zip two sorted runs together with a two-finger merge.
- The guaranteed-O(n log n), stable workhorse — no bad inputs exist.
- O(n) auxiliary buffer; allocate it once, not per recursion.
- left <= right on ties is the stability linchpin.
- The only mainstream sort that works beyond RAM (external sorting).
- Best sort for linked lists: sequential access, O(1) list-splice merges.
- Midpoint as lo + (hi - lo) / 2 to dodge integer overflow.