The idea: keep only the head of each list in a heap

You have k lists, each already sorted, with n items in all, and you want one sorted list. The next output item is always one of the k list heads (the first item not yet taken from each list). So put the heads in a min-heap: the root is the smallest head, which is the next output item. The heap holds at most k entries, never n.

Four sorted lists L0 to L3 with their current heads 8, 5, 9 and 4 boxed in red. The heads sit in a min-heap with 4 at the root, 5 and 9 below it and 8 under 5. The output already holds 1, 2, 3 and 4 comes next
The heap holds one head per list; its root is the next item of the merged output.

The algorithm

heap = empty
for each list i:  push (first item of i, i)          # build: k pushes
while heap not empty:
    (v, i) = pop the root                             # smallest head
    output v
    if list i has another item w:  push (w, i)        # refill from the SAME list

Each entry is a pair (value, list number), so the page can tell where a popped item came from. The colours on the canvas show the same thing: every item keeps its list's colour from the list, through the heap, into the output (Demo: merge 4 sorted lists: 26 comparisons for 12 items).

Why the root is always next

Every item still waiting in list i is at least list i's head, because the list is sorted. Every head is at least the root, because the heap is a min-heap. So nothing waiting anywhere is smaller than the root. This is why the heap only needs the heads: the rest of each list cannot win yet.

Pop and refill: replace the top

After the root is popped, only its own list lost a head, so only that list has a new candidate. Libraries do the pop and the push as one operation: the new item goes straight into the root and sifts down (Python's heapq.heapreplace does exactly this). Sift-down compares the two children (1 comparison), then the smaller child with the item (1 more), and stops as soon as the item is not bigger, so it costs at most 2 log2 k comparisons (Demo: one Next).

Step 1: the root 4 from L3 is popped to the output. Step 2: L3's next item 6 replaces the root; its smaller child is 5, so they swap. Step 3: 6 has one child, 8, which is bigger, so the sift-down stops with 5 at the root
The replacement comes from the list that just lost its head, then sifts down until heap order holds.

When a list runs out

If the popped item was the last of its list, there is nothing to push. The heap shrinks by one: its last entry moves to the root and sifts down, exactly like a heap's remove-min. The heap ends empty when every list is used up (Demo: a list runs out).

Equal keys and stability

When two heads are equal, the page compares the list numbers too, so the item from the lower list goes first. If the lists are in their original order (as the runs of a merge sort are), equal items come out in their original order: the merge is stable. Comparing values alone would still give a sorted output, but equal items from different lists could come out in any order (Demo: equal keys).

Cost: O(n log k)

Every item is pushed once and popped once, and each costs O(log k) because the heap never holds more than k entries. Building the heap costs O(k log k) here (or O(k) with a bottom-up build).

MethodTimeExtra space
Scan all k heads for every itemO(n k)O(1)
Merge pairs of lists, log2 k roundsO(n log k)O(n) per round
Heap of the k heads (this page)O(n log k)O(k)
Concatenate everything and sortO(n log n)O(n)

With k = 8 runs of 2 the heap used 61 comparisons, where scanning 8 heads for every item would use 16 × 7 = 112 (Demo: k = 8 runs of 2). With k = 2 the heap has just two entries, and each step is the single comparison of the merge step in merge sort (Demo: k = 2: 7 comparisons for 8 items).

Where it is used

  • External merge sort: sort chunks that fit in memory into runs on disk, then merge all runs in one pass, with one input buffer per run and a heap of the buffers' heads. A database sorting a big ORDER BY does this.
  • LSM-tree compaction: several sorted files (SSTables) are merged into one, newest version of a key first.
  • Merging sorted streams: sort -m, Python's heapq.merge, merging time series or log files by timestamp, "merge k sorted linked lists".
  • Search engines: walking several sorted posting lists in document order.

See also: the heap itself, with sift-up and sift-down, on Heaps and Priority Queues; sorting with a heap on Heap Sort; the two-way merge inside merge sort on Quick Sort vs Merge Sort; and sorted runs being merged on LSM Tree vs B-Tree.

Merging runs two at a time in passes, instead of all at once with a heap, is shown on Bottom-up Merge Sort.

What the page leaves out

The loser tree (tournament tree), which external sorts often use instead of a heap because it needs only log2 k comparisons per item; the bottom-up O(k) heap build; disk buffers, read-ahead and how many runs fit in one merge pass; replacement selection, which makes runs longer than memory; removing duplicates while merging.