Merge sort — every question, written out
Split until trivially sorted, then merge sorted halves. The canonical divide-and-conquer, and the sort that guarantees O(n log n). Stable, but needs O(n) space.
Read the merge sort explanation and watch it run
Why is merge sort O(n log n) on every input, not just on average?
Complexity derivation
The merges at any depth write n elements between them, and halving gives log n depths
At any single depth the merges cover disjoint ranges whose sizes add up to n, and each merge writes every element of its range exactly once — so a whole level costs n writes regardless of the values. Ranges halve going down, giving ceil(log₂ n) levels, and n per level times log n levels is the bound. Nothing in that argument mentions the input, which is why the bound holds unconditionally.
See it run — The prompt asks how many elements this one merge writes — the answer is the range size, exactly.
How deep does the recursion go when merge sort runs on 16 elements?
Complexity derivation
Four levels of splitting, since 16 halves to 8, 4, 2 and finally 1
The recursion stops when `lo >= hi`, so it splits until every range is a single element: ceil(log₂ 16) = 4 levels. The frames panel shows exactly this, bottoming out at `sort(0..0)` with depth 4. Depth is fixed by the size alone, which is the other half of the unconditional bound.
An interviewer asks for merge sort’s space complexity. What is the honest answer?
Complexity derivation
O(n), because the scratch buffer dominates the O(log n) recursion stack
Both terms are real, but they add rather than compete: O(n) for the buffer plus O(log n) for the stack, and O(n) swallows the smaller term. Claiming O(log n) is the single most common way a good merge sort answer is undone, because it hides the very cost that makes quicksort attractive. Say O(n) auxiliary, then name the stack as the second term.
Why does the merge need a scratch buffer at all, when the output goes back into the same array?
Trade-off & selection
Writing the output into the range would overwrite elements of the halves that have not been read yet
The merge writes to `a[out]` starting at `lo`, while the right half still has unread elements sitting further along in that same range — write first and you destroy data you are about to need. Snapshotting the range into `buffer` decouples reads from writes, and that snapshot is the O(n) charge. Prism draws it as its own row above the bars, so the memory the header claims is literally on screen.
See it run — The final merge: the buffer row holds a copy of all 16 values before a single one is written back.
Follow-up: could you merge the two halves in place and drop the buffer entirely?
Trade-off & selection
It is possible, but the known techniques are slow or intricate enough that nobody ships them
In-place merging is a solved problem on paper — block rotations and symmetric merges achieve it — but the constants and the code complexity are bad enough that real libraries buy the buffer instead. That is the honest framing: the O(n) space is a deliberate purchase, not an oversight. If the buffer is genuinely unaffordable, the practical answers are heapsort for the in-place guarantee, or a linked list where merging relinks nodes and needs no buffer at all.
Follow-up: the data is a singly linked list instead of an array. What changes?
Comparison
The buffer disappears — merging relinks existing nodes — so the extra space drops to the stack alone
On a list the merge sets `next` pointers instead of copying values, so the two sorted runs are woven together with no auxiliary storage at all. That is why merge sort is the list sort in practice and quicksort is not: quicksort needs random access to partition, which a list charges O(n) for. The bottom-up variant goes further and removes the recursion too, giving genuinely O(1) extra space.
Both sorts average O(n log n). What decides which one a library ships?
Comparison
Stability and a hard worst-case ceiling, bought with O(n) memory that quicksort does not spend
Java ships quicksort-family for primitive arrays and TimSort for objects, and the split is exactly this trade: primitives cannot observe stability, so the in-place sort wins, while objects with multiple keys need it. Merge sort also refuses to have a bad day, which matters wherever tail latency is a contract rather than an average. You pay O(n) memory for both properties.
Follow-up: the data is 500 GB and your machine has 16 GB. How does merge sort adapt?
Trade-off & selection
Sort memory-sized chunks, spill each as a sorted run, then k-way merge the runs in one streaming pass
The merge step only ever reads its inputs front to back, which is the one access pattern spinning disks and network storage are built for. So the external shape is ordinary merge sort with the merge reading from files: sort what fits, write sorted runs, then merge them with one buffered reader each and a small heap picking the minimum. This is what database engines actually run, and it is why merge sort owns the out-of-core case outright.
Where exactly does merge sort’s stability live in the code?
Invariant identification
In the `<=` of the front comparison, which sends ties to the left half
The left half holds the elements that came earlier in the original array, so taking left on a tie preserves their relative order and taking right destroys it. That is the whole mechanism: one character, `<=` rather than `<`, in one comparison. It is also why stability bugs are so quiet — no test that sorts plain numbers can possibly detect the difference.
See it run — Every key is equal, so every comparison is a tie — and every take comes from the left half.
What must be true for a merge to be allowed to look only at the two front elements?
Invariant identification
Both halves are already sorted, so each half’s smallest remaining value is at its front
Sortedness is precisely the promise that a run puts its smallest remaining candidate on top, so the overall minimum of the two runs must be one of the two fronts and nothing deeper needs looking at. The recursion establishes it: single elements are trivially sorted, and every merged range is sorted by this same argument. The invariants panel restates it before each merge with the actual index ranges filled in.
What does this merge sort do when handed an array that is already sorted?
Edge case reasoning
Almost exactly the same work — it still splits fully and copies every range into the buffer
Prism records 460 steps for random input and 446 for sorted input at the same size — indistinguishable, because the split pattern depends only on the indices. That indifference is the guarantee, and it is simultaneously the criticism: real data is often partly ordered, and merge sort charges full price for it anyway. TimSort exists precisely to reclaim that discount by detecting existing runs before merging.
See it run — Already sorted, and the final merge still snapshots all 16 values and writes all 16 back.
Which two ranges does the very first merge of a 16-element run actually combine?
Trace prediction
`a[0..0]` with `a[1..1]` — two single elements, at the deepest level
Top-down merge sort recurses all the way to a single element before it merges anything, so the first merge is the smallest possible one, at the deepest level of the left spine. Work happens on the way back up, not on the way down. The frames panel makes the order concrete: `sort(0..0)` and `sort(1..1)` push and pop, and only then does a merge step appear.
See it run — The first merge step in the whole run, combining two ranges of one element each.
Someone writes `if (buffer[left - lo] < buffer[right - lo])` instead of `<=`. What breaks, and when do you find out?
Code diagnosis
Stability dies silently; only a sort of records by a second key ever reveals it
The output is still sorted, so every test that checks sortedness passes and the bug ships. Equal keys have simply been reordered, which only matters once something depends on a previous sort — the classic sort-by-name-then-by-department pipeline. Test stability by sorting objects on one field and asserting on another, because no test over bare numbers can ever see it.
A merge is rewritten to read `a[left]` and `a[right]` directly and write to `a[out]`, with no buffer. What goes wrong?
Code diagnosis
Writes to the front of the range clobber left-half elements that have not been read yet
`out` and `left` both start at `lo`, so the first take from the right half writes over `a[lo]` while the left half still needs to read it. The array quietly fills with duplicated values, and because the result is often still ordered, small tests can pass. The snapshot is what makes the merge safe, which is why the buffer is a correctness device before it is a cost.
Why does the implementation compute `(lo + hi) >> 1` rather than `(lo + hi) / 2`?
Edge case reasoning
To floor the result to an integer index; in fixed-width languages the same line also risks overflow
Array indices must be integers, and `>> 1` floors in one operation where `/ 2` in JavaScript would hand back 3.5. The deeper habit belongs to fixed-width languages: `lo + hi` can overflow a signed 32-bit int on a large array, which is the same bug that lived in binary search implementations for years. `lo + ((hi - lo) >> 1)` is the version that is safe everywhere, and worth writing by reflex.
Explain merge sort to someone who does not code. Say it out loud before revealing.
Explain it plainly
Imagine two people each holding a neat stack of exam papers, already in order by score. Combining them is mindless: both look at their top paper, whoever has the lower one hands it over, repeat. You never dig into either stack, because a sorted stack always keeps its next-best candidate on top. Merge sort just manufactures those sorted stacks out of nothing — a single paper is already a sorted stack, so cut the pile in half, cut again, keep cutting until every pile is one paper, then merge them back in pairs. Each round of merging doubles the pile size, so after about four rounds you have covered sixteen papers and after twenty you have covered a million. Where the picture cheats: with paper, you merge into your hands. In a computer the papers live in numbered slots, and you cannot lay the combined pile back down on top of the two halves without burying papers you have not read yet — so you photocopy the range first and merge from the copy. That photocopy is the catch, and it is why merge sort needs as much spare room as the data it is sorting.
A strong answer earns the recursion rather than asserting it, and does not skip the awkward part: the merge needs somewhere to put its output. Naming that cost unprompted is what separates an explanation from a recitation.