Why is heap-based k-way merge O(N log k) but merging the k sources pairwise in a loop O(N*k)?
answer
- count how many times one element gets copied
- the accumulator keeps growing each round
- sum of an arithmetic series in the loop version
- heap: exactly one insert, one extract per element
- k/2 versus log k as the per-element factor
basics
~20 sThe heap touches each element twice, at log k cost each. Merging source after source into one growing accumulator re-copies everything already accumulated on every round, so the earliest elements are copied about k times.
solid answer
~50 sIn the heap version each element is inserted once and extracted once from a heap of at most k entries, so total work is `O(N log k)`. In the loop version you merge source 1 with source 2, then that result with source 3, and so on. On round j the accumulator already holds roughly `j*N/k` elements and every one of them is re-copied by the merge. Summing `N/k + 2N/k + ... + N` gives about `N*k/2`, so `O(N*k)`. With k = 200 that is a hundredfold difference at the same asymptotic input size. The fix does not have to be a heap: pairing the sources tournament-style — merge them two at a time in rounds, halving the count each round — also gives `O(N log k)`, because every element is copied once per round and there are `log k` rounds.
go deeper
Recall the two costs: a heap-based merge is O(N log k), and merging one source at a time into a growing result is O(N*k). Being able to state both and say which is better is enough at this level.
Derive both bounds on the spot. Show the accumulator being re-copied each round and sum the series, then show that the heap touches every element exactly twice at log k cost each.
Compare the two O(N log k) schemes rather than stopping at the bound: the heap streams with O(k) space, tournament pairing needs intermediates but parallelises. Say which fits the pipeline in front of you and why.
Own the call between merging in the data path and avoiding the merge altogether — pushing ordering to the producers, or indexing. Justify accepting an asymptotically worse but simpler approach when the dataset comfortably fits memory.
## The setup Two hundred servers, each with a timestamp-sorted log file, N lines in total. You want one chronological feed. Almost every candidate reaches for the same first idea: "I already know how to merge two sorted sequences, so I will just do it 199 times." That idea is correct and quadratic-ish, and being able to say exactly *why* is the point of this question. ## Accounting for the sequential loop Suppose for simplicity each source holds `N/k` lines. Merge source 1 into source 2: the merge walks both inputs and writes `2N/k` lines. Now merge that result with source 3: it walks `2N/k + N/k` lines and writes `3N/k`. And so on. The total number of element touches is `2N/k + 3N/k + 4N/k + ... + N` which is an arithmetic series summing to roughly `N*k/2`. In big-O terms, `O(N*k)`. The structural reason is that the accumulator is re-read on every round. A line from source 1 is touched in round 1, again in round 2, again in round 3 — about k times in all. The work is not in the comparisons being expensive; it is in copying the same data over and over. ## Accounting for the heap The heap version never builds an accumulator. Each line enters the heap once, waits, and leaves once. The heap holds at most k entries, so an insert or an extract costs `O(log k)` sift steps. Two operations per line, N lines: `N * 2 * log k = O(N log k)` With k = 200, `log k` is under 8. The loop version's factor is 100 (that is `k/2`). Same input, same output, a factor of roughly 12 in touches — and the gap widens linearly as you add servers, because the loop's factor grows with k while the heap's grows with `log k`. ## The third option nobody expects you to mention The heap is not the only way to reach `O(N log k)`. Pair the sources up: merge 1 with 2, 3 with 4, 5 with 6, and so on, producing `k/2` sequences. Repeat. After `log k` rounds you have one sequence. Every round touches every element exactly once, so the total is `N log k` — identical asymptotically to the heap. What differs is everything else: | Approach | Time | Extra space | Streaming? | |---|---|---|---| | Sequential accumulator | O(N*k) | O(N) for the accumulator | no | | Tournament pairing | O(N log k) | O(N) for intermediates | no | | Heap of heads | O(N log k) | O(k) for the heap | yes | The heap's real advantage over tournament pairing is not asymptotic time but **space and latency**: it holds k live elements instead of materialising intermediate merged sequences, and it emits output from the very first extraction rather than after the last round. That is why it, and not the pairing scheme, is what disk-based merging is built on. Tournament pairing, on the other hand, parallelises beautifully — each pair in a round is independent — so on a cluster it can be the better answer. ## Where candidates get the direction wrong A few reversals are worth naming, because interviewers listen for them: - **"The heap is faster because comparisons are cheaper."** No. Both approaches perform comparisons of the same cost. The heap wins by not re-touching settled elements. - **"Sequential merging is fine because each individual merge is linear."** Each merge is linear *in its own inputs*, and its inputs keep growing. Linear-per-round times k rounds with a growing round size is the quadratic-ish term. - **"O(N log k) is better than O(N log N), so the heap beats sorting by a lot."** It is better, but only by the ratio `log k / log N`, which for k = 200 and a large N is maybe a factor of three or four in comparisons. The dramatic win over sorting is the memory profile, not the comparison count. - **"Just concatenate and sort, the runtime's sort is very fast."** A defensible engineering answer when everything fits in memory and N is modest — and admitting that is a strength, not a weakness. It stops being defensible the moment the data exceeds memory or the consumer needs early output. ## The takeaway When an interviewer describes many sorted inputs and one sorted output, they are usually probing whether you can price the naive loop. Derive `N*k/2` out loud, derive `N log k` out loud, and then state which of the two `O(N log k)` schemes you would use and why. That sequence — naive cost, better cost, choice justified by space and streaming rather than by asymptotics alone — is the complete answer.
- Is there a way to reach O(N log k) without using a heap at all?Yes — pair the sources up and merge in rounds, halving the number of sequences each round. After `log k` rounds one sequence remains, and each round touches every element once, so the total is `N log k`. It matches the heap on time but not on space: it materialises intermediate merged sequences and emits nothing until the final round, whereas the heap holds only k live elements and streams output from the first extraction.
- How does k-way merging compare with just concatenating everything and sorting it?Sorting the concatenation costs `O(N log N)` comparisons versus `O(N log k)`, which for k far below N is a modest constant-factor win. The decisive difference is memory and latency: sorting needs all N elements resident and produces nothing until it finishes, while the merge needs only k heads and emits from the first step. When everything fits comfortably in memory, concatenate-and-sort is a perfectly defensible engineering call.
- Does the sequential-loop cost change if the sources have wildly different sizes?Yes, and it is exploitable. The cost is driven by how much data the accumulator carries through each round, so merging the largest sources last keeps the accumulator small for longer. Ordering the sources smallest-first is the same idea that makes greedy optimal-merge orderings work. It improves the constant substantially but does not change the `O(N*k)` shape in the worst case.
saying these in an interview costs you the question
- Says the loop is fine because each merge is linear
- Claims the heap wins by making comparisons cheaper
- Cannot derive the arithmetic series for the loop
- Thinks a heap is the only route to O(N log k)
- Confuses log k with log N when pricing the merge