Run it
The merge itself, hand-rolled and against the standard library.
The first claim - laziness - which it does win on.
And the claim that does not hold: materialising the whole thing.
Why the heap is size k and not N
The next value in the merged output must be the smallest unconsumed value, and because each input is already sorted, each list's smallest unconsumed value is its head. So only k values are ever candidates — one per list — and the heap needs to hold exactly those.
That is the whole complexity argument. N values come out, each costing one pop and at most one push on a heap of size k, giving O(N log k). Concatenating and sorting is O(N log N), and log k is smaller than log N whenever k is smaller than N — which is the usual case, with many long lists.
The tag, and what happens without it
The heap entries are tuples: (value, list_index, position). The list index is not decoration — it is how you know which list to pull the successor from. Storing bare values loses that, and the merge cannot continue.
The index also settles ties deterministically, which matters when values are equal: the tuple comparison falls through to the list index and the merge becomes stable. And if the values are objects that are not comparable, the tuple will try to compare them and raise — which is why the index goes second, not third, in implementations that need to avoid that.
What the standard library gives you, and the honest measurement
heapq.merge(*lists) is this algorithm, and it returns a generator: it never materialises the result, so memory is O(k) rather than O(N), and the first value is available immediately.
The editor below measures both claims and the second one is worth seeing. Asking for just the smallest value takes 0.3 ms lazily against 140 ms if you sort first — a few hundred times less work for the same answer. But materialising everything is the other way round: sorted(concatenation) beats list(heapq.merge(...)), often by two or three times, because Timsort is C and detects the sorted runs while heapq.merge is a Python-level generator paying per-item overhead.
So the honest answer has two halves: O(N log k) is the right algorithmic answer, and in CPython you reach for heapq.merge when the input streams or does not fit, and for sorted() when it does.
Where this actually gets used
External sorting: split a file too large for memory into sorted chunks, then k-way merge the chunks back. That is what sort(1) does, and it is why the merge has to be lazy — the whole point is that the result does not fit either.
The same structure merges sorted posting lists in a search index, combines time-ordered log files, and is the merge step of an LSM-tree compaction. Any time several sorted streams have to become one, this is the shape, and the heap is the part that makes it O(N log k) rather than O(Nk).
What to say out loud
A min-heap with one entry per list, each tagged with which list it came from. Pop the smallest, emit it, push the next value from that same list. The heap stays at size k, so it is O(N log k) for N total values. heapq.merge does exactly this and is lazy, which is the version I would use for streams. If everything fits in memory and I just want a sorted list, concatenating and calling sorted is usually faster in CPython, because Timsort exploits the existing runs in C.
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
Empty lists in the input. The initial heap must skip them or the first index lookup raises. It is the easiest line to omit.
Non-comparable values. The tuple falls through to the tie-break field, so if two values are equal and the next field is not comparable, the comparison raises. Putting an integer index second avoids it.
Lists of very different lengths. Correctness is unaffected, and one list dominating means the heap is mostly the same entry - still O(N log k), and worth saying if asked about the worst case.
The follow-ups interviewers ask
"What if there are millions of lists?" Then the heap is the bottleneck rather than the data, and the answer is to merge in rounds - pair them up and merge repeatedly, which is O(N log k) with a much smaller constant, or shard the merge across machines.
"Merge two sorted lists without a heap." Two indices and a comparison. For k = 2 the heap is pure overhead, and a good interviewer will ask you to notice that.
"How does external sorting use this?" Split the input into chunks that fit in memory, sort each and write it out, then k-way merge the files back. That is what sort(1) does, and it is why the merge must be lazy - the output does not fit either.
Common wrong answers
"Concatenate and sort - it is the same complexity." It is O(N log N) against O(N log k), and it needs the whole thing in memory. That said, the editor shows it winning the clock in CPython, so the honest answer names both facts rather than one.
"Push all the values into one heap." O(N) memory instead of O(k), which defeats the purpose. The heap should hold candidates, not data.
"heapq.merge sorts the inputs for you." It does not. It assumes each input is already sorted, and produces silently wrong output if one is not.
Recap in one screen
- The heap holds one entry per list - at most k, never N.
- Each popped value is replaced by its own list's successor, which is what keeps the merge correct.
- A list that runs out simply stops being represented.
- Worth trying: Set K to 2 and compare again. With two lists the heap buys almost nothing and sorted() wins more clearly - log k of 2 is 1.
- Worth trying: Merge lists of unequal length, including an empty one. The if lst guard in the initial heap is what stops an IndexError, and it is easy to forget.