K-way Merge Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
Merge many sorted lists by keeping only the current front of each list in a min-heap.
3 sub-patterns · 9 questions
What is this pattern?
You have K lists that are each already sorted: arrays, linked lists, the rows of a matrix, or lists you never write down (multiples of 2, 3 and 5). You want to read all of them as one sorted stream: merge them, find the Kth smallest item, or find a range that touches every list.
The key fact: the next smallest item overall must be at the front of one of the lists. Everything behind a front is bigger than that front. So you only ever need to compare K candidates, one per list. Keep those K fronts in a min-heap. Pop the smallest, write it out, then push the next item from the same list. The heap never holds more than K items.
Cost: each of the N items is pushed and popped once, and each heap operation costs O(log K), so the total is O(N log K). Sorting everything costs O(N log N). When K is much smaller than N, the heap wins.
K checkout queues, each already sorted by ticket number, and one person at the exit calling the lowest number. They only need to look at the person at the front of each queue. Nobody further back can have a lower ticket than their own queue's front. Call the lowest front out, and the next person in that queue steps up.
See it move
Heap shown in pop order, top on the left; a real heap stores it as a tree. `5(L1)` = value 5 from list L1. In the lists, red = already popped, blue = currently in the heap.
L0 = [1,4,7], L1 = [2,5,8], L2 = [3,6,9,10]step 1/11- heap size
- 3
- K lists
- 3
Each list is sorted, so its smallest item is its front. Push the 3 fronts (1(L0), 2(L1), 3(L2)). The heap never holds more than 3 items.
Heap shown in pop order, top on the left. `9(L1)` = value 9 from list L1. In the lists, red = dropped, blue = currently in the heap. The candidate range is always [heap top, curMax].
L0 = [4,10,15,24,26], L1 = [0,9,12,20], L2 = [5,18,22,30]step 1/10- curMax
- 5
- best
- none
Push the front of each list: 4(L0), 0(L1), 5(L2). The heap always holds exactly one item per list, and curMax = 5 is the largest of them.
How do I recognise it?
The input is several lists, arrays or rows that are each sorted.
"Merge K sorted …", or "output everything in sorted order".
"Kth smallest" across sorted rows or columns, or "K pairs with the smallest sums" from two sorted arrays.
A matrix whose rows and columns are sorted: each row is one sorted list.
"Smallest range that includes at least one number from each list".
Numbers built from smaller ones (ugly numbers,
x·2,x·3,x·5): each multiplier gives its own sorted stream.An array that is almost sorted (each item at most k places from where it belongs).
Looks like K-way Merge, but isn't
With K = 2, a heap is overkill: compare the two fronts directly. The heap only pays off when there are many lists to choose from.
There are no sorted lists to merge. Keep a heap of size K of the best items seen so far, not a heap of list fronts.
Popping k times costs O(k log n). Binary search on the value with a staircase count (how many cells are ≤ mid?) costs O(n log(max − min)) whatever k is. Both are fine for interviews; know that both exist.
If you need overlaps or gaps, think in intervals: merge them, then walk the result. A heap over the lists can feed that walk (Employee Free Time), but the merging logic belongs to Intervals.
How would I discover it from scratch?
Don't memorise “use k-way merge”. Ask these questions in order — the pattern falls out.
Pour every item from every list into one array and sort it: O(N log N). It works, but it throws away the fact that each list was already sorted.
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Merge K sorted
4 questionsProduce the full merged order. The heap holds one front per list; pop the smallest, write it out, push its successor.
Kth smallest across lists
4 questionsDon't build the whole merge: pop from the merged stream k times. Each list can be a row of a matrix, a numerator's fractions, or a row of pair sums.
Smallest range
1 questionsKeep exactly one item from every list in the heap, track the largest of them, and repeatedly replace the smallest.
Don't mix these up
K-way Merge: the input is K sorted lists, and the heap holds one front per list. Top K: the input is one unsorted collection, and the heap holds the K best items seen so far.
Pushing all N items and popping them is just heap sort: O(N log N). The point of K-way merge is that the heap holds at most K items, so each operation is O(log K).
With two lists, compare the fronts directly (two pointers). With k lists, either use a heap or merge them in pairs (divide and conquer). Both cost O(N log k); merging one list at a time costs O(N·k).
Code templates (C++)
Merge K sorted arrays
The heap holds (value, array, index), one per array. Pop the smallest, then push the next item from the same array. priority_queue is a max-heap by default, so greater<> makes it a min-heap.
// Merge K sorted arrays: the heap holds one front per array.
vector<int> mergeKArrays(vector<vector<int>>& arrs) {
// (value, array, index); greater<> turns priority_queue into a min-heap
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
for (int a = 0; a < (int)arrs.size(); a++)
if (!arrs[a].empty()) pq.push({arrs[a][0], a, 0}); // skip empty arrays
vector<int> out;
while (!pq.empty()) {
auto [v, a, i] = pq.top(); pq.pop(); // smallest front overall
out.push_back(v);
if (i + 1 < (int)arrs[a].size())
pq.push({arrs[a][i + 1], a, i + 1}); // its successor takes its place
}
return out;
}Kth smallest across sorted rows
Seed the heap with the first item of each row; only min(rows, k) rows can matter. Pop k − 1 times, each time pushing the popped cell's right neighbour. The top is now the kth smallest.
// Kth smallest in a matrix whose rows (and columns) are sorted: pop k times.
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq; // (value, row, col)
for (int r = 0; r < min(n, k); r++) pq.push({matrix[r][0], r, 0}); // rows past k can't matter
for (int pops = 1; pops < k; pops++) { // throw away the k-1 smallest
auto [v, r, c] = pq.top(); pq.pop();
if (c + 1 < (int)matrix[r].size()) pq.push({matrix[r][c + 1], r, c + 1});
}
return get<0>(pq.top()); // the kth pop
}Smallest range covering K lists
One item per list in the heap plus a running curMax. Each step: the range [top, curMax] is a candidate; pop the top and push its successor, updating curMax. Stop as soon as a list runs out: without it, no range covers every list.
// Smallest range [lo, hi] containing at least one number from each sorted list.
vector<int> smallestRange(vector<vector<int>>& nums) {
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq; // (value, list, index)
int curMax = INT_MIN;
for (int l = 0; l < (int)nums.size(); l++) {
pq.push({nums[l][0], l, 0}); // exactly one item per list
curMax = max(curMax, nums[l][0]);
}
vector<int> best = {get<0>(pq.top()), curMax};
while (true) {
auto [v, l, i] = pq.top(); pq.pop(); // [v, curMax] covers every list
if ((long long)curMax - v < (long long)best[1] - best[0]) best = {v, curMax};
if (i + 1 == (int)nums[l].size()) break; // list l ran out: no more full ranges
pq.push({nums[l][i + 1], l, i + 1});
curMax = max(curMax, nums[l][i + 1]); // the new item may be the new max
}
return best;
}