In external merge sort, why can run generation start before the total input size is known?

## The loop, and what it does not reference Run generation in an external merge sort is a plain streaming loop: ``` runs = 0 while not end_of_input(stream): m = 0 while m < capacity and not end_of_input(stream): buffer[m] = next(stream) m = m + 1 sort(buffer[0..m-1]) write_run(buffer[0..m-1]) runs = runs + 1 ``` Read it looking for the total input size. It is not there. The loop consults exactly two conditions: has the stream ended, and is the buffer full. The invariant that holds after every outer iteration is: *every record consumed so far now lives on durable storage inside some sorted run of at most `capacity` records, and the buffer is free.* Peak memory is `capacity` regardless of how long the stream turns out to be. This matters more than it first looks, because the natural mental model of an offline algorithm is "measure the input, plan the work, execute the plan". Applied here it produces a wrong answer that sounds reasonable: *first find `n`, divide by memory to get the run count, then decide the merge shape.* You do not need any of that, and on some inputs you cannot get it. A live event stream has no length. A pipe has no length. A compressed archive's decompressed size is unknown until it is decompressed — and measuring it means a full extra read of the whole thing, which is precisely the pass you were trying to avoid. ## The run count is discovered, not planned The merge phase does need the run count, but it runs *after* phase one, when the count is a known constant. Nothing about the merge has to be committed to in advance: - **Fan-in** is set by memory and buffer size, not by the number of runs. It is known before phase one even starts. - **The number of merge rounds** falls out of `ceil(log_fan-in(runs))` once `runs` is known. - **Grouping** is decided at merge time. If the runs exceed the fan-in, merge them in groups of at most fan-in each, producing longer runs, and repeat until one remains. A related misconception is that the run count should be a power of the fan-in, or that all runs must be the same length. Neither is true. The last run is almost always partial, and when the run count is not an exact multiple of the fan-in the merge simply handles a smaller final group. Runs of unequal length merge correctly and cost, in bytes moved, exactly what their sizes say they cost. ## Making runs longer than memory The fill-sort-spill loop produces runs of exactly `capacity`. There is a classic refinement — **replacement selection** — that produces longer ones. Keep the buffer full and, instead of sorting and dumping it wholesale, repeatedly emit the smallest record that is still greater than or equal to the last one emitted, refilling the vacated slot from the input stream. Records that arrive too small to belong in the current run are held aside for the next one. On randomly ordered input this yields runs averaging about **twice** the sort memory, and on input that is already nearly ordered it can produce one enormous run and finish the whole sort in effectively a single merge — which is the point: fewer runs means a lower chance of needing an extra merge pass. The tradeoff is real. Replacement selection interleaves reads with per-record selection work and gives up the wholly sequential fill-then-sort pattern, so it is less friendly to prefetching and to memory locality; it is also more code to get right, particularly the boundary between the current run and the held-aside next one. On modern hardware, where fan-in is often large enough that one merge pass suffices anyway, doubling the run length frequently buys nothing — which loops right back to the pass-count arithmetic. It earns its keep when the run count sits just above a pass boundary, or when the input is known to arrive partly ordered, as timestamped event streams usually do. ## What still needs care on an unknown-length stream Streamwise generation is not entirely free of surprises. You cannot preallocate output capacity, so the storage for runs has to grow as you go, and you should be prepared for the input to be far larger than anyone predicted — the run count is unbounded from the algorithm's point of view. You also cannot report progress as a percentage, only as bytes consumed. And if the stream is genuinely live, "sorted" only ever means sorted over what has been consumed: a total order requires the stream to be closed. That is a different problem from external sorting, and the honest answer in an interview is to name the distinction rather than pretend the merge can emit final results early.