K-way Merge Pattern

When to use K-way Merge

• You need to merge K already-sorted lists, arrays, or linked lists into one sorted output.
• You need to find the smallest range that contains at least one element from each of K sorted lists.
• You need the kth smallest pair sum (or product) drawn from two sorted arrays.
• You need to find a specific position in the union of several sorted streams without materializing the full union.
• You can move forward in each input one element at a time without going back (no random access needed).

Template

function mergeKSortedLists(lists) {
  const heap = new MinHeap();
  for (let i = 0; i < lists.length; i++) {
    if (lists[i] !== null) {
      heap.push([lists[i].val, i, lists[i]]);
    }
  }
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.size > 0) {
    const [, , node] = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next !== null) heap.push([node.next.val, 0, node.next]);
  }
  return dummy.next;
}

Common mistakes

• Forgetting to include a tiebreaker in the heap entry — when two heads have equal values, comparing the raw objects causes a runtime error in many languages.
• Pushing every element of every list into the heap upfront, which costs O(N log N) space and time instead of O(N log K).
• Not advancing the pointer in the source list after popping the head; the algorithm stalls because every pop pushes the same element back.
• Using a max-heap by accident (e.g. reversed comparator) and returning elements in the wrong order.
• Returning `dummy` instead of `dummy.next` and exposing the placeholder node to the caller.