K-Way Merge

## The problem shape You operate a fleet of 200 servers. Each one writes its own log file, and each file is already in timestamp order because each server appends as events happen. Now you want a single chronological feed across the whole fleet for incident review. You have 200 sorted sequences and want one sorted sequence — that is the k-way merge, with k = 200. ## The key observation At any moment, what is the next line of the merged feed? It must be the oldest line that has not been emitted yet. Because every source is internally sorted, the oldest unemitted line of any source is that source's *current head*. So the global next line is the minimum over just k values — one per source — not a minimum over all N remaining lines. That single observation is the whole pattern. You never need more than k live candidates, and a min-heap is exactly the structure that gives you "smallest of k" repeatedly while accepting replacements cheaply. ## The loop 1. **Seed.** For each source i, take its first element and insert it into the min-heap. Each heap entry is a composite record: the ordering value (here, the timestamp), the source identifier i, and the position within that source. 2. **Extract.** Pull the minimum out of the heap. That value is the next element of the merged output; emit it. 3. **Refill.** The extracted entry came from source i. Take the *next* element of source i and insert it. If source i has nothing left, insert nothing — the heap simply shrinks. 4. **Repeat** until the heap is empty. An empty heap means every source has been drained. At every point the heap holds at most one entry per source, so its size is bounded by k, and it starts at k and only shrinks as sources run dry. ## Why the source identifier matters A beginner version stores only the values. Then the extraction tells you *what* the smallest value was but not *which* source produced it, so you cannot fetch its successor — and if you re-scan the sources to find out, you have thrown away the entire advantage. Storing the source identifier (and, if the source is not itself a cursor you can advance, the position within it) is not a decoration; it is the mechanism. ## The cost Every one of the N elements enters the heap exactly once and leaves exactly once. Each of those two operations costs `O(log k)` because the heap holds at most k entries. Total: `O(N log k)` time. Extra space is `O(k)` for the heap itself, plus whatever buffering each source needs. Compare the naive alternative of concatenating all 200 files and sorting the result: that is `O(N log N)` comparisons and, worse, it requires all N lines resident at once. With 200 servers' worth of logs, N is enormous and k is 200. `log k` is about 8 while `log N` might be 30, and the memory difference is the difference between "runs on a laptop" and "does not run". ## What the pattern buys beyond speed - **Streaming.** Output is produced incrementally. The consumer can start reading the merged feed before the inputs have been fully read, and you can stop early if you only wanted the first few thousand lines. - **Bounded memory.** Memory depends on k and the per-source buffer size, not on the data volume. This is precisely why the pattern underpins merging phases in disk-based sorting: the whole dataset never has to fit. - **Order preservation within a source.** Because a source's next element only enters the heap after its predecessor has left, elements of one source can never be emitted out of order relative to each other. ## Recognising it in an interview Interviewers rarely say "use a heap". They say: "you have many already-sorted feeds and need one merged feed", or "give me the smallest values across many sorted sequences without materialising everything". Both descriptions are the same machine: heap of heads, extract, emit, refill. The moment you hear *many* sorted inputs and *one* sorted output, size the heap at k, not at N, and remember to tag each entry with where it came from. A final calibration: when k is small — two or three sources — the heap is technically correct but constant factors make a direct comparison of the heads simpler and faster. The heap earns its keep when k is large enough that scanning all k heads on every emitted element would itself dominate.