K-Way Merge

Merge k sorted lists, or pick items by rank across them, with a min-heap that holds one candidate per list. N items cost O(N log k).

Overview

The idea

Merge sort merges two sorted lists by looking at their two front items and taking the smaller one. K-way merge does the same with k lists. At every step the next output item is the smallest of the k front items. A min-heap that holds exactly those k items finds it in O(log k), and the heap never grows past k.

Each heap entry must remember where it came from, so the next item can be pulled from the same list. In Python the entry is a tuple (value, list index, position). Tuples compare item by item, so equal values are broken by list index and two positions are never compared to each other.

Trace: merging three lists

Merge [1, 4, 5], [1, 3, 4] and [2, 6]. The heap starts with the three front items, written as (value, list, position).

start — (1,0,0) (1,1,0) (2,2,0)
1 — (1,0,0) — (4,0,1) — (1,1,0) (2,2,0) (4,0,1) — 1
2 — (1,1,0) — (3,1,1) — (2,2,0) (3,1,1) (4,0,1) — 1 1
3 — (2,2,0) — (6,2,1) — (3,1,1) (4,0,1) (6,2,1) — 1 1 2
4 — (3,1,1) — (4,1,2) — (4,0,1) (4,1,2) (6,2,1) — 1 1 2 3
5 — (4,0,1) — (5,0,2) — (4,1,2) (5,0,2) (6,2,1) — 1 1 2 3 4
6 — (4,1,2) — list 1 is empty — (5,0,2) (6,2,1) — 1 1 2 3 4 4
7 — (5,0,2) — list 0 is empty — (6,2,1) — 1 1 2 3 4 4 5
8 — (6,2,1) — list 2 is empty — empty — 1 1 2 3 4 4 5 6

Eight items, eight pops, and the heap never held more than three entries. At step 5 the two entries with value 4 are ordered by list index, which is the tie-break at work.

Why O(N log k)

N is the total number of items across all lists. Every item is pushed once and popped once, and each heap operation costs O(log k) because the heap has at most k entries.

Scan the k fronts for each output item — O(N k) — O(1) — simple, slow when k is large
Merge list 1 with 2, then with 3, and so on — O(N k) — O(N) — early items are copied up to k times
Pair up lists, merge pairs, repeat (divide and conquer) — O(N log k) — O(N) — log k rounds, each copies N items
Min-heap of k fronts — O(N log k) — O(k) — works on streams; only k items in memory
Concatenate and sort — O(N log N) — O(N) — ignores that the inputs are sorted

The heap and the divide-and-conquer approach share the same bound. The heap wins when the lists are streams or files that do not fit in memory, because it only ever needs k items at once.

Variant: the k-th smallest in a sorted matrix

If every row is sorted, the rows are k sorted lists. Seed the heap with the first item of each row, then pop k times. The k-th pop is the answer. Popping k times from a heap of at most n rows costs O(k log n), and you only need to seed min(k, n) rows.

Trace on the matrix with rows [1, 5, 9], [10, 11, 13], [12, 13, 15] and k = 8.

1 — 1 — (5,0,1) (10,1,0) (12,2,0)
2 — 5 — (9,0,2) (10,1,0) (12,2,0)
3 — 9 — (10,1,0) (12,2,0)
4 — 10 — (11,1,1) (12,2,0)
5 — 11 — (12,2,0) (13,1,2)
6 — 12 — (13,1,2) (13,2,1)
7 — 13 — (13,2,1)
8 — 13 — (15,2,2)

The 8th smallest is 13. When the columns are sorted too, a second method works: binary search on the value. For a candidate value x, count the items that are at most x by walking a staircase from the bottom-left corner in O(n) steps, then move the search range. Each round costs O(n), and there are about log(max - min) rounds.

1 — 1 to 15 — 8 — 2 — too few, search 9 to 15
2 — 9 to 15 — 12 — 6 — too few, search 13 to 15
3 — 13 to 15 — 14 — 8 — enough, search 13 to 14
4 — 13 to 14 — 13 — 8 — enough, search 13 to 13

The range closes on 13. Both methods are correct; say which you chose and why.

Variant: k pairs with the smallest sums

Given two sorted arrays a and b, the pair sums form a grid where each row (fixed a[i]) is sorted by j and each column is sorted by i. Treat each row as a list: seed the heap with (a[i] + b[0], i, 0) for the first min(k, len(a)) rows, then pop k times and push (i, j + 1) after each pop.

Trace for a = [1, 7, 11], b = [2, 4, 6], k = 3.

1 — 3, (0, 0) — (1, 2) — (5, 0, 1) — (5,0,1) (9,1,0) (13,2,0)
2 — 5, (0, 1) — (1, 4) — (7, 0, 2) — (7,0,2) (9,1,0) (13,2,0)
3 — 7, (0, 2) — (1, 6) — row 0 is exhausted — (9,1,0) (13,2,0)

Only 3 pops for k = 3, and the heap never held more than 3 entries. Pushing every pair up front would cost O(len(a) times len(b)), which is the mistake to avoid.

Variant: the smallest range that covers every list

Find the shortest interval [lo, hi] that contains at least one item from each of k sorted lists. Run the k-way merge and keep track of the largest value currently in the heap. At every step the heap holds one item from each list, so [heap minimum, current maximum] is a valid range. Record the best one, then advance the list that owns the minimum. Stop when any list runs out, since after that no range can cover every list.

Trace for the lists [4, 10, 15, 24, 26], [0, 9, 12, 20] and [5, 18, 22, 30].

1 — 0 — 5 — 0 to 5 — 5 — 0 to 5
2 — 4 — 9 — 4 to 9 — 5 — 0 to 5
3 — 5 — 10 — 5 to 10 — 5 — 0 to 5
4 — 9 — 18 — 9 to 18 — 9 — 0 to 5
5 — 10 — 18 — 10 to 18 — 8 — 0 to 5
6 — 12 — 18 — 12 to 18 — 6 — 0 to 5
7 — 15 — 20 — 15 to 20 — 5 — 0 to 5
8 — 18 — 24 — 18 to 24 — 6 — 0 to 5
9 — 20 — 24 — 20 to 24 — 4 — 20 to 24

At step 9 the minimum 20 is the last item of list 2, so the merge stops. The answer is 20 to 24.

External sorting: the same merge on disk

When data does not fit in memory, sort it one memory-sized chunk at a time and write each sorted chunk, called a run, to disk. Then k-way merge the runs, reading each one from the front. The heap holds one item per run, so memory depends on the number of runs, not on the data size. PostgreSQL's EXPLAIN ANALYZE shows for each Sort node whether it ran in memory or on disk, which is this technique at work.

The pattern in Python, Java and JavaScript

Ready-made k-way merge — heapq.merge(*lists), a lazy iterator — none; write the loop over PriorityQueue — none; write a small heap class
Heap entry — tuple (value, list, position) — an int[] or a small record with a comparator — an object with a comparator
Tie-break between equal values — the list index in the tuple — the comparator decides; equal keys are fine — same
Comparing numbers in a comparator — not needed — Integer.compare(a, b), never a - b — (a, b) => a - b is safe for small integers

heapq.merge takes key and reverse keyword arguments and does not load all the input into memory, so it is the right tool for merging sorted files or logs.

What you will be able to do

Merge k sorted arrays, lists or streams in O(N log k) with a heap of k entries, and explain why the bound holds.
Trace the heap contents by hand on a small input, including how ties are broken.
Turn the k-th smallest in a matrix, k smallest pair sums and smallest covering range into the same merge.
Compare the heap with divide-and-conquer merging and binary search on the value, and pick one for the given constraints.

When to use it

Merging k sorted arrays, linked lists or streams into one sorted output
The k-th smallest item across sorted rows, such as a matrix with sorted rows
The k pairs with the smallest sums from two sorted arrays
The smallest range that contains at least one item from each of k sorted lists
Sorting data that does not fit in memory: sort runs, then merge them
Any two-way merge that has grown to k inputs

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio