K-Way Merge

Foundations

So far, the heap chose among items it held all at once. Now, what if the items arrive as several sorted lists, and you need one sorted output without collecting everything first?

Every list is sorted, so the smallest value not yet merged is one of the lists' current heads. Keep a min-heap of exactly one head per list. Pop the top, append it to the output, and push the next value from the same list. With k lists the heap never holds more than k items, so each of the N values costs O(log k).

Split nums = [7, 1, 5, 3, 6] into two runs and sort each: [1, 5, 7] and [3, 6]. The heap starts with heads 1 and 3. Popping 1 brings in 5; popping 3 brings in 6; then 5, 6, and 7 follow. The output is [1, 3, 5, 6, 7], and the heap held two items the whole time, one per run.

• Sentinel (Dummy) Head & Merging

  Merging two lists picks the smaller head. Merging k lists does the same with a heap choosing among k heads.

  Open lesson

Case Scenario

Merge k Sorted Lists gives k sorted linked lists and asks for one sorted list. The heap holds each list's current head node, keyed by its value, so the next node to attach is always on top. For lists = [[1, 4, 5], [1, 3, 4], [2, 6]], the merged list is [1, 1, 2, 3, 4, 4, 5, 6].

The direct approach copies every value into one list, sorts it, and builds a new linked list. That costs O(N log N) for N nodes in total and throws away the order each list already had, treating the inputs as if they were random.