Merge sort

The problem it solves

Some sorting jobs cannot tolerate a bad day. A database engine sorting a join, a system sorting records by one key and then another without scrambling the first pass, a process sorting far more data than fits in memory — these need three properties quicksort can’t promise: a guaranteed O(n log n) whatever the input, stability (equal elements keep their relative order), and a shape that works on sequential access (streams, linked lists, disk runs). Merge sort delivers all three, and charges O(n) extra space for the privilege.

That bill explains the division of labour in real standard libraries: quicksort-family for primitive arrays where stability is meaningless, merge-family (TimSort) wherever stability is owed.

The intuition — and where it breaks down

Two piles of exam papers, each already sorted by grade. Combining them is mindless: compare the two top papers, take the better one, repeat. You never look deeper than the tops, because sorted piles put their best candidate on top. Merging two sorted piles of total size n costs n comparisons at most — one per paper taken.

Merge sort’s move is to conjure sorted piles out of nowhere: a single paper is trivially a sorted pile. So split the stack in half, keep splitting until every pile is one paper, then merge pairs of piles back up. Each level of merging doubles pile sizes; log₂ n levels later, one sorted stack.

Where the analogy breaks: with paper, “splitting” is free and “merging” happens into your hands. In an array, merging needs somewhere to put the output — you cannot interleave two adjacent sorted halves in place without stomping on unread elements. That’s the O(n) buffer, and it isn’t incidental; in-place merging exists in the literature but is complicated enough that nobody ships it. The buffer is the price of the guarantee.

Loading…

A walkthrough you can check

Sort [8, 3, 5, 1].

1. Split to [8, 3] and [5, 1]; split again to singletons — four trivially-sorted piles.
2. Merge [8] and [3]: fronts are 8 and 3, take 3, then 8 → [3, 8]. Merge [5] and [1] → [1, 5].
3. Merge [3, 8] and [1, 5]: fronts 3 vs 1 → take 1. Fronts 3 vs 5 → take 3. Fronts 8 vs 5 → take 5. Left half exhausted → drain 8. Result [1, 3, 5, 8].

Note what the final merge cost: three comparisons and four writes for four elements. Every element is written once per level, and comparisons never exceed writes. The visualization shows the two halves highlighted as regions and asks you, mid-merge, which front gets taken — the answer is always just “the smaller of two numbers”, which is the point: merge sort is a big result assembled from the smallest possible decision.

The invariant

Every range handed to a merge is already sorted, and the merge’s output is sorted because it only ever appends the smallest remaining candidate. The recursion makes the first half true (singletons are sorted; merged ranges are sorted by the second half); the second half is true because both remaining candidates’ minimums are sitting at the fronts.

The tie-break rule hides inside that invariant: when fronts are equal, take from the left half. That single convention is the entirety of merge sort’s stability — the left half’s elements came earlier in the original array, so taking left-first preserves original order among equals. Write < instead of <= in one comparison and stability silently dies; no small test catches it unless the test sorts objects by one field and checks another.

Complexity, derived

Two factors, both visible in the trace. Per level: the merges at any depth cover disjoint ranges whose sizes sum to n, and each merge writes each of its elements exactly once — n writes per level, at most n comparisons. Levels: ranges halve going down, so ⌈log₂ n⌉ levels of splitting and the same coming back up. Multiply: O(n log n), unconditionally — the prediction prompt in the visualization asks you to compute a merge’s write count in advance precisely because “size of the range, exactly” is the fact the whole bound stands on.

Compare against the reversed and random presets: the comparison counter barely moves between them. That indifference is the guarantee, and it’s also the criticism — merge sort does full work on inputs that are nearly sorted already, which is the gap TimSort exploits by detecting existing runs.

Space: the O(n) buffer, plus O(log n) recursion stack. For linked lists the buffer vanishes — merging relinks nodes in place — which is why merge sort is the list sort.

What people get wrong

Computing the midpoint as (lo + hi) / 2 in fixed-width languages — same overflow as binary search, same fix: lo + (hi − lo) / 2.

Copying at the wrong moment. The merge must read from a snapshot of the range while writing into the range; reading and writing the same live cells interleaves garbage. Copy the range into the buffer first, then merge buffer → array.

“It’s O(log n) space because recursion.” The recursion is O(log n); the buffer is O(n), and the buffer dominates. Claiming O(log n) total space in an interview undoes an otherwise good answer.

Allocating a fresh buffer per merge. Correct but slow — one shared buffer allocated once serves every merge, and the difference is measurable at scale.

Implementation notes across languages

Python’s and JavaScript’s built-in sorts are TimSort — merge sort with run detection and insertion sort below a threshold; when asked “how does your language sort?”, that is the answer, and “merge-based, therefore stable” is the follow-through. Java uses TimSort for objects (stability contract) but not primitives (no observable stability) — a distinction interviewers enjoy. For linked lists in any language, bottom-up merge sort (merge runs of 1, 2, 4…) avoids recursion entirely and needs O(1) extra space; the top of LeetCode’s “Sort List” problem is exactly this. External sorting — data on disk — is merge sort’s other kingdom: sort memory-sized chunks, then k-way merge the sorted runs with a heap.