vizlearn

Merge k sorted sequences

Interview QuestionsBy Updated

Keep a heap holding one candidate per list. Pop the smallest, emit it, and push that list's successor — so the heap never exceeds k and each of the N values costs one log k operation. heapq.merge is this, lazily. Its real win is memory, not speed: for materialising everything, sorted() is usually faster.

Heaps & top-kCoding problemHard

Step through it

What to watch

  • 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.

Say this 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."

Overview

To merge k sorted sequences, keep one current candidate from each sequence in a min-heap. Repeatedly emit the smallest and replace it with that sequence’s next value, for O(N log k) time.

Run it

The merge itself, hand-rolled and against the standard library.

1Python
Output
The first claim - laziness - which it does win on.
2Python
Output
And the claim that does not hold: materialising the whole thing.
3Python
Output

                

                

                    
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).

                

                

                    
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.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
The hand-rolled merge, then both of heapq.merge's claims measured - the laziness it does win on, and the full materialisation it does not.
How the code works
  1. (lst[0], i, 0)Value, which list, and where in it. The list index is what lets you pull the successor after a pop — without it the merge cannot continue.
  2. if ci + 1 < len(lists[li])The replacement comes from the same list as the value just emitted. That is the invariant: one candidate per live list, so the heap stays at k.
  3. next(heapq.merge(*lists))The laziness claim, as a measurement. A few hundred times less work than sorting to get the same first value.
  4. list(heapq.merge(*lists))And the claim that does not hold: materialising everything is slower than concatenating and sorting, because Timsort is C and already exploits the sorted runs.
Change one thing
  • 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.
  • 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.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. How large does the heap get?
  2. Why does each heap entry carry the list index?
  3. What is heapq.merge's actual advantage over sorted(concatenation)?
  4. Where does the k-way merge get used in practice?




        
    



 Cheat sheet
Merge k sorted sequences
Merge k sorted lists with a min-heap. Push one element per list, pop the smallest, refill, and see why the total cost is O(n log k).
INTERVIEW · vizlearn.in/interview/merge-k-sorted-sequences.html
More in Interview
InterviewFind the median of a data streamInterviewWrite binary search without an off-by-oneInterviewFirst and last position of a targetInterviewBinary search on the answer, not the array
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact