K-way Merge

Min-Heap of K Sorted Lists

1:00

How to merge k sorted lists into one sorted output in O(n log k) time using a min-heap of the k current heads.

By the end, you can

Explain why each list's head is sufficient to determine the next output element.
Compare the three merging strategies (dump-and-sort, scan-k-heads, min-heap) by complexity and trade-off.
Trace a k-way merge step-by-step for small inputs, showing which element is popped and which list refills.
Implement the seeding phase correctly, skipping empty lists.
Identify and fix the three sharp-edge pitfalls: empty-list seeding, tie-breaking via list index, and wrong-list refill.
Derive the O(n log k) time and O(k) space bounds from the algorithm's structure.
Recognize where k-way merge appears in practice (external sort, merge sort, sorted stream merging, tournament trees).

Up next in Coding Interview Patterns