Merge Sort

The 10-second versionCopy Anchor Link

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves into one sorted array. The merge is the trick: two already-sorted lists combine in a single linear pass by repeatedly taking the smaller of the two front elements. Splitting keeps halving, so there are about log n levels, and each level does O(n) work — giving O(n log n) in the best, average, and worst case. It's stable, it has no bad input, and it costs O(n) extra space for the merge buffer.

Why this existedCopy Anchor Link

Early machines didn't sort in RAM; they sorted data on magnetic tape, which you could only read forwards, one pass at a time, and rewinding was slow. That constraint made the merge — an algorithm that reads two sorted streams and writes one — enormously valuable, because it turns "read everything a hundred times" into "read everything once per level."

• 1945 — John von Neumann describes what we now call merge sort, one of the very first algorithms ever written down for a stored-program computer. It shows up in his work on the EDVAC.
• 1948 onward — Merging becomes the backbone of external sorting: tape drives read sorted runs and merge them two at a time until one sorted tape remains.
• Today — TimSort (Python, Java), Rust's stable sort, and the sort command's external mode are all merge sorts in disguise.

Why it mattered then: it was the first sort whose worst case was provably good. No matter how malicious the input, you got O(n log n) — a guarantee, not a hope. That guarantee is what let people trust it with the data centers of the day.

Inside the inventor's headCopy Anchor Link

Here's the puzzle von Neumann is chewing on: sorting is O(n²) if you compare everything to everything, and that's brutal. Can one comparison do more than place two elements?

The pivot is to notice that merging is easier than sorting. Take two piles that are already sorted. To merge them, look at the top of each pile and take the smaller — repeat. You never need to look deeper: the top of a sorted pile is its smallest element, so the smaller of the two tops is the smallest element overall. That's a single linear pass, no comparison wasted.

Now the leap: if merging is cheap, then create sorted piles by merging even smaller piles, all the way down to piles of one element (which are trivially sorted). Halve, halve, halve, then merge back up. That's divide and conquer.

The first attempt misses the point of the merge. To combine two sorted arrays, the naive instinct is "stick them together and re-sort" — which throws away the order you fought for. The good merge uses two fingers, one on each sorted stream:

// Naive: insert every element of b into a one at a time → O(n²) in the worst case.function mergeNaive(a, b) {  const out = a.slice();  for (const x of b) {    let i = out.length;    out.push(x);    while (i > 0 && out[i - 1] > x) { out[i] = out[i - 1]; i--; }    out[i] = x;  }  return out;}// Two-finger merge: one linear pass, O(a.length + b.length).function merge(a, b) {  const out = [];  let i = 0, j = 0;  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);  while (i < a.length) out.push(a[i++]);  while (j < b.length) out.push(b[j++]);  return out;}

The final approachCopy Anchor Link

Top-down recursion: split at the midpoint, sort both halves, merge. (There's also a bottom-up version that merges runs of size 1, then 2, then 4 — same result, no recursion.)

The invariant: at the top of every call, sort(a, lo, hi) rearranges only a[lo..hi) and leaves it sorted. The merge rests on a second invariant — during the merge, the smallest not-yet-output element is always at one of the two cursors — which is exactly why looking only at the two fronts is enough.

A worked trace: one mergeCopy Anchor Link

Merging the sorted runs [3, 27, 38] and [9, 10, 43, 82]:

Seven elements, six comparisons. That's the linear pass doing its job — compare-and-take, never a wasted look.

It in codeCopy Anchor Link

function mergeSort(a) {  if (a.length <= 1) return a.slice();   // 0 or 1 element: already sorted  const mid = a.length >> 1;  const left = mergeSort(a.slice(0, mid));  const right = mergeSort(a.slice(mid));  const out = [];  let i = 0, j = 0;  while (i < left.length && j < right.length)    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;}

ComplexityCopy Anchor Link

The log n comes from halving: there are about log n levels before runs are single elements. The n comes from each level merging the entire array once. Multiply them and it's O(n log n) — and crucially, that never degrades, not for sorted input, not for reverse-sorted input, not for an adversary's worst case.

The O(n) extra space is the price. Where quicksort sorts in place, merge sort needs a second array as big as the input (in-place merging exists but is slower and rarely used).

Where you meet it todayCopy Anchor Link

• TimSort. Python's sorted and list.sort are TimSort — a merge sort that first finds naturally sorted runs, extends them with insertion sort, then merges. Stability is why sorted(data, key=...) preserves input order on ties.
• Java and Rust. Arrays.sort(Object[]) and Rust's stable sort are merge-family sorts. If you ask for stability, you're asking for a merge sort.
• External sorting. Sorting 500 GB on a machine with 8 GB of RAM: sort chunks that fit in memory, write them out, then merge the sorted runs. This is the sort command's -m mode and how databases build indexes.

// JavaScript's Array.prototype.sort has been stable since ES2019 —// ties keep their input order, for free.const byScore = rows.slice().sort((a, b) => a.score - b.score);

RecapCopy Anchor Link

• Merge sort: split in half, sort each half, merge. Merging two sorted runs is a single linear pass.
• It guarantees O(n log n) in every case — the first popular sort to make that promise.
• It is stable, which is why libraries hand it the "keep ties in order" job.
• The cost is O(n) extra space, and it's the workhorse of external sorting on disk and tape.

Next up: Quick Sort — the same divide-and-conquer skeleton, but it sorts in place and lives on the edge of O(n²).