Intermediate 9 min read

K-way merge

In one line

To merge k sorted lists, keep only the current head of each list in a min-heap; repeatedly pop the smallest and push its successor from the same list, for O(N log k) time over N total items.

What it is

K-way merge combines k sorted sequences into one sorted sequence. With two lists you compare two heads (the merge step of merge sort). With k lists, comparing all k heads at every step costs O(k) per item; a min-heap of the k heads cuts that to O(log k).

Each heap entry remembers where it came from, typically (value, list index, position). When you pop the smallest, you push the next item from that same list. The heap therefore never holds more than k entries, one per list that still has items.

Why interviewers ask

Merge K Sorted Lists (LeetCode 23) is one of the most asked hard problems, and the same pattern solves Kth Smallest Element in a Sorted Matrix (378), Find K Pairs with Smallest Sums (373) and Smallest Range Covering Elements from K Lists (632). Interviewers check that you avoid concatenate-and-sort, carry the source index in the heap entry, handle empty lists and ties, and can state O(N log k).

How it works

1Push the first item of every non-empty list into a min-heap as (value, list_index, position). The list index also breaks ties so Python never compares non-comparable payloads like linked-list nodes.
2Pop the smallest entry and append its value to the output.
3If that list has a next item, push (next_value, list_index, position + 1).
4Repeat until the heap is empty. Every item is pushed once and popped once, each costing O(log k), so the total is O(N log k).
5For 'k-th smallest' variants, stop after the k-th pop instead of merging everything.

Worked example · Merge [1, 4, 5], [1, 3, 4], [2, 6]

Start: heap = (1, L0, 0), (1, L1, 0), (2, L2, 0).
Pop (1, L0): out = [1]. Push L0's next, (4, L0, 1). Heap: 1(L1), 2(L2), 4(L0).
Pop (1, L1): out = [1, 1]. Push (3, L1, 1). Heap: 2(L2), 3(L1), 4(L0).
Pop (2, L2): out = [1, 1, 2]. Push (6, L2, 1). Heap: 3(L1), 4(L0), 6(L2).
Pop 3 from L1: out = [1, 1, 2, 3]. Push (4, L1, 2). Heap: 4(L0), 4(L1), 6(L2).
Pop 4 from L0 (tie broken by list index 0 < 1): push (5, L0, 2). Pop 4 from L1: L1 is finished, push nothing.
Pop 5: L0 finished. Pop 6: L2 finished. Heap empty.
Output: [1, 1, 2, 3, 4, 4, 5, 6]. The heap never held more than 3 entries.

Picture it

Picture k checkout lines, each already sorted by ticket number. A manager only looks at the person at the front of each line, always calls the lowest ticket among those fronts, and then the next person in that line steps up to the front.

Reference code

import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))   # (value, which list, index)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)            # smallest current head
        out.append(val)
        if j + 1 < len(lists[i]):                  # replace it with its successor
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out

The heap holds one entry per list: the current smallest unused item, tagged with its list and position. Popping gives the global minimum; pushing that list's next item keeps the heap at most k large. For linked lists use (node.val, i, node) so the index breaks ties before Python tries to compare nodes.

Key patterns

Merge k sorted lists or arrays

When: LeetCode 23 or merging sorted files

How: Heap of (value, list_index, position); pop smallest, push its successor.

K-th smallest in a sorted matrix

When: Rows and columns sorted (LeetCode 378)

How: Treat each row as a list; push each row's first item, pop k times. Binary search on the value range is an alternative.

K pairs with smallest sums

When: Two sorted arrays, smallest pair sums (LeetCode 373)

How: Push (a[i] + b[0], i, 0) for each i; on pop, push (a[i] + b[j + 1], i, j + 1).

Smallest range covering k lists

When: Find the narrowest range with one item from each list (LeetCode 632)

How: Heap of heads plus a running maximum; the range is [heap min, max]; advance the list of the minimum until one list runs out.

Real-world use

External sorting in databases

When data is too big for memory, databases such as PostgreSQL sort chunks into sorted runs on disk, then merge the runs with a heap-based k-way merge, reading each run sequentially.

LSM-tree storage engines

RocksDB, LevelDB and Cassandra keep data in many sorted files (SSTables). Reads and compactions merge them with a merging iterator built on a heap, so the newest version of each key comes out in key order.

Log aggregation

Merging time-ordered logs from many servers into one timeline (for example, 'sort -m' on already sorted files, or collectors merging per-host streams) is a k-way merge keyed by timestamp.

Search engines

Combining sorted posting lists from many index shards or segments into one ranked or doc-ID-ordered list uses the same heap-of-heads approach.

In a project

You need to produce one sorted CSV of 2 billion transactions by timestamp for an auditor, but your machine has 16 GB of RAM and the data is 200 GB spread across 400 daily files that are each already sorted.

Open all 400 files with buffered readers so each read pulls a few megabytes at a time.
Push the first row of each file into a min-heap keyed by (timestamp, file_index).
Pop the smallest row, write it to the output buffer, and push the next row from the same file.
If a file is not sorted, first sort it in memory-sized chunks to create sorted runs, then merge the runs the same way.

Impact: The merge uses memory for only 400 rows plus I/O buffers and reads every file sequentially once, so the job runs in a single pass at disk speed instead of failing with out-of-memory errors or needing a cluster.

Trade-offs

Use it when

The inputs are already sorted (lists, files, index segments, streams)
k is large enough that scanning all k heads per item is too slow
The data does not fit in memory and must be streamed

Avoid it when

k = 2: a plain two-pointer merge is simpler and faster
Inputs are not sorted: sort them or use a different approach
Everything is small and in memory: concatenating and sorting may be simpler code

Cost: O(N log k) time for N total items across k lists; O(k) heap space (plus the output). Pairwise divide-and-conquer merging also gives O(N log k); concatenate-and-sort gives O(N log N).

Common mistakes

Pushing all N items into the heap at once, which costs O(N) memory and O(N log N) time.
Forgetting to carry the list index, so you do not know which list to advance after a pop.
Pushing linked-list nodes without a tie-breaker, causing TypeError when two values are equal.
Not skipping empty lists at the start, which crashes on lst[0].
Merging lists one by one into a growing result, which is O(N k) instead of O(N log k).

Interview questions

Quick revision

Heap holds one head per list: (value, list_index, position).
Pop smallest -> output -> push next item from the same list.
Time O(N log k), space O(k).
Tie-breaker index avoids comparing nodes in Python.
Skip empty lists when seeding the heap.
K-th smallest: stop after k pops.
Used in external sort, LSM-tree compaction and log merging.

Check yourself

1. What is the time complexity of merging k sorted lists with N total items using a heap?

2. After popping an item from list 2, what do you push?

3. Why include the list index in each heap entry in Python?

4. What is the maximum number of entries in the heap at any time?

Heap basics Merging & splitting lists Merging sorted sequences Divide and conquer

Saved on this device. Create a free account to keep it on every device.

Top-K problems Two heaps (running median)

Practise this with Sam

A real mock interview, out loud, with an honest scorecard. Free to start.

Start free