K-Way Merge Pattern

CodingSenior2 min read · 3 problemsUpdated Nov 11, 2026

Use a min-heap of k pointers (one per list) to merge k sorted sources in O(N log k).

When to Use It

Merge k sorted lists, smallest range covering k lists, kth smallest in a sorted matrix.

Classic example: Merge k sorted linked lists.

How It Works

A min-heap holding one pointer per sorted source lets you always know the global minimum across all sources in O(log k). Pop it, advance that source's pointer, push the next value from that source. Repeat until all sources are exhausted. Total work: O(N log k) where N is the total number of elements across all k lists.

The pattern generalizes the 2-way merge of mergesort. Crucially, it beats the naive 'concatenate-then-sort' (O(N log N)) whenever k < N, which is almost always. It's the right tool for external sorting: when data doesn't fit in memory, sort chunks, then k-way merge the sorted chunks back.

A common variant is 'smallest range covering k lists': maintain one pointer per list in a min-heap, also track the current max across the heap; the range [min, max] covers all k lists. Pop the min, advance, update max, repeat: shrinking the range whenever possible.

Key Insight

A min-heap of one pointer per source gives O(log k) access to the global minimum across k sorted streams, reducing the merge from O(N * k) (linear scan per pop) to O(N log k).

Min-heap of (value, list_idx). Pop smallest, push next from that list.

Templates

// import java.util.*;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < lists.size(); i++) {
    if (!lists.get(i).isEmpty()) {
        pq.offer(new int[]{ lists.get(i).get(0), i, 0 });
    }
}
List<Integer> merged = new ArrayList<>();
while (!pq.isEmpty()) {
    int[] top = pq.poll();
    int val = top[0], listIdx = top[1], elemIdx = top[2];
    merged.add(val);
    if (elemIdx + 1 < lists.get(listIdx).size()) {
        pq.offer(new int[]{ lists.get(listIdx).get(elemIdx + 1), listIdx, elemIdx + 1 });
    }
}
return merged;

import heapq

heap = []
for i, lst in enumerate(lists):
    if lst:
        heapq.heappush(heap, (lst[0], i, 0))
merged = []
while heap:
    val, list_idx, elem_idx = heapq.heappop(heap)
    merged.append(val)
    if elem_idx + 1 < len(lists[list_idx]):
        heapq.heappush(heap, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
return merged

Common Pitfalls

Pushing all N elements into the heap up-front (O(N log N)) instead of maintaining only k pointers (O(N log k)).
Forgetting to handle empty input lists, which would crash if you try to push their first element unconditionally.
Using value-only heap entries when you need (value, listIdx, elementIdx) to advance the correct list after a pop.
In 'smallest range', forgetting to update the running max when pushing a new element, returning a range that doesn't cover all lists.
For 'kth smallest in sorted matrix', failing to use the row/column structure, you can use binary search on value for O(n log(max-min)) instead.

Variations

Merge k sorted linked lists: heap of (val, listIdx) or divide-and-conquer pairwise merging.
Kth smallest in sorted matrix: heap-based k-way merge of rows, or binary search on value.
Smallest range covering elements from k lists: heap + running max.
External sort: chunk-and-merge for data larger than memory.
Merged feeds: Design Twitter seeds a max-heap with each followee's newest tweet and pops the 10 most recent.

Big O

Time: O(N log k)
Space: O(k)

Each of the N total elements across k lists is pushed and popped once on a heap of size k. The heap holds at most one pointer/value per list.

Next Pattern0/1 Knapsack (DP)