Your billion-record merge sort blows its memory ceiling — how do you shrink the auxiliary space without losing the O(n log n) guarantee?

## Separate three different memory costs When a merge sort is accused of using too much memory, three distinct quantities get conflated: 1. **Peak live auxiliary memory** — the most extra bytes alive at any instant. For array merge sort this is `Theta(n)` element slots. 2. **Total allocation churn** — how many bytes pass through the allocator over the run. This can be far larger than the peak, and it is often the real symptom (allocator pressure, fragmentation, pauses). 3. **Recursion stack** — `O(log n)` frames, roughly 30 at a billion elements. Real, bounded, and never the cause of a memory ceiling breach in this algorithm. The common misconception is that merge sort needs `O(n log n)` extra space, arrived at by multiplying "a buffer per level" by "log n levels". It does not: buffers at different levels are not simultaneously live in the way that reasoning assumes, and the sizes down a root-to-leaf path form a geometric series `n + n/2 + n/4 + ... = 2n`, which is still `O(n)`. ## Fix 1 — one buffer, hoisted above the recursion The worst common implementation allocates a fresh temporary array at the top of every merge. That is roughly `2n` slots allocated at each of `log n` levels, so on the order of `n log n` slots passing through the allocator, all of it short-lived garbage. Peak live memory is unchanged, but throughput suffers badly and memory fragments. The fix is structural: allocate one buffer of size n before the first recursive call and thread it through, letting each merge use the slice `buf[lo..hi-1]`. Zero allocations inside the recursion, identical output, and the merges no longer touch the allocator at all. At a billion records this is usually the entire difference between a job that runs and one that thrashes. ## Fix 2 — the half-buffer trick The merge does not need both runs copied out. Copy only the **left** run into the buffer, then merge the buffer against the right run — which is still sitting in the array — writing results back into the array starting at `lo`. The write cursor never overtakes the right run's read cursor, because every write consumes exactly one element from one of the two sources and the right run is already positioned ahead. The buffer drops to `n/2`, and the tie-break rule that preserves stability is unchanged: on a tie, take from the buffered left run. ## Fix 3 — ping-pong between two arrays An alternative that removes the copy-back entirely: keep two arrays of size n and alternate their roles level by level, merging from A into B at one level and from B into A at the next. This costs a permanent `2n` footprint rather than `1.5n`, but every element is written exactly once per level instead of copied twice. It is the natural formulation for the bottom-up variant, where levels are explicit passes. ## "Can't you just merge in place?" This is the follow-up that separates a rehearsed answer from a real one. In-place merging of two adjacent sorted runs **is** possible — but it is not free: - The obvious approach, shifting or rotating elements to open a slot whenever the right run's head must move left, is easy to write and degrades to quadratic work in the merge. - Rotation-based schemes such as symmerge do the merge with `O(1)` auxiliary space but raise the merge cost to `O(n log n)`, pushing the total higher than the classic algorithm. - Block-merge schemes get much closer to linear merging with `O(1)` extra space by carving an internal buffer out of the array itself, and stable variants exist — at the price of large constant factors, subtle correctness arguments and a great deal of code that few teams want to own. So the honest answer is: yes, but you are trading a well-understood linear buffer for constants, complexity and maintenance risk. Do it only when the memory ceiling is genuinely immovable, and consider first whether the workload actually needs a stable sort — if not, a guaranteed `O(n log n)` sort that is in-place by construction is a much cheaper way to get to `O(1)` auxiliary space. ## When the data itself does not fit At a billion records the question often is not the buffer at all: the array does not fit. That is external sorting, and merge sort is the natural fit because merging is purely sequential — it reads each input forward, once. Sort chunks that fit in memory, write each out as a sorted run, then merge the runs in a streaming pass. Sequential reads and writes are what storage is good at, and the algorithm never needs random access to the data it is merging. ## How to answer this in an interview Name the three costs, say `O(n)` peak with confidence, then diagnose rather than prescribe: where is the temporary allocated, is the buffer hoisted, is the copy-back needed, and does the dataset even fit? Finish with the honest in-place caveat. Confidently reciting `O(n)` and stopping is a middle-level answer; the diagnosis is the senior one.