CodeWithYash

Intermediate · Module 14 · Lesson 5

K-way merge

Merge multiple sorted sources with a frontier heap.

15–25 min readLesson 81 of 123

Lesson 81 of 123

1d streak

K-Way Merge: Merging K Sorted Streams in O(N log K)

Merging $k$ sorted lists with $N$ total elements naively takes $O(k cdot N)$. By maintaining a Min-Heap of size k containing the current head of each list, we find the minimum element in O(log k) time, yielding O(N log k) overall.

MergeKSortedLists.java
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        lists.length, (a, b) -> Integer.compare(a.val, b.val)
    );

    // 1. Insert initial head of each non-empty list
    for (ListNode head : lists) {
        if (head != null) minHeap.offer(head);
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    // 2. Poll smallest node and advance its pointer
    while (!minHeap.isEmpty()) {
        ListNode smallest = minHeap.poll();
        tail.next = smallest;
        tail = tail.next;

        if (smallest.next != null) {
            minHeap.offer(smallest.next);
        }
    }
    return dummy.next;
}

Cost Model

Complexity & Trade-offs

Push / pop
O(log n)
O(n)
Reading the root is O(1); heap construction is O(n).

When to use it

  • Top-k, streaming medians, scheduling, and best-first frontiers.
  • Repeated access to an extreme without fully sorting.
  • Merging sorted sources.

Common mistakes

  • Choosing the wrong heap direction for a bounded top-k set.
  • Assuming heap iteration is globally sorted.
  • Claiming bottom-up heap construction is O(n log n).

Practice prompts

  • Reproduce the worked K-way merge example without looking at the trace.
  • Change one input condition and explain whether the K-way merge invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.