Merging Sorted Lists

algorithmintermediateTime O(n log k)Space O(k)

Two sorted lists merge into one by looking only at their heads: the smaller head is the smallest thing anywhere, so it goes next. With linked lists nothing needs to be copied, the chosen node is simply unhooked from its list and hung on the tail of the merged one, and when either list runs out the rest of the other is already in order. With k lists the same idea needs the smallest of k heads at each step, which is exactly what a min-heap of the heads provides.

3 sorted lists. A min-heap holds one head per list, so the smallest of all the heads is always at the top. Pop it, hang it on the merged tail, and push its successor. Nodes are relinked, never copied.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.

Heads: a = 1, b = 2, c = 3. Which node is taken next?
- 1 from a
- 2 from b
- 3 from c
Answer: 1 from a. The smallest head goes next, straight off the top of the heap.
Heads: a = 6, b = 2, c = 3. Which node is taken next?
- 6 from a
- 2 from b
- 3 from c
Answer: 2 from b. The smallest head goes next, straight off the top of the heap.
Heads: a = 6, b = 5, c = 3. Which node is taken next?
- 6 from a
- 5 from b
- 3 from c
Answer: 3 from c. The smallest head goes next, straight off the top of the heap.
Heads: a = 6, b = 5, c = 4. Which node is taken next?
- 6 from a
- 5 from b
- 4 from c
Answer: 4 from c. The smallest head goes next, straight off the top of the heap.
Heads: a = 6, b = 5, c = 9. Which node is taken next?
- 6 from a
- 5 from b
- 9 from c
Answer: 5 from b. The smallest head goes next, straight off the top of the heap.
Heads: a = 6, c = 9. Which node is taken next?
- 6 from a
- 9 from c
Answer: 6 from a. The smallest head goes next, straight off the top of the heap.
Heads: a = 8, c = 9. Which node is taken next?
- 8 from a
- 9 from c
Answer: 8 from a. The smallest head goes next, straight off the top of the heap.

How it runs, step by step

3 sorted lists. A min-heap holds one head per list, so the smallest of all the heads is always at the top. Pop it, hang it on the merged tail, and push its successor. Nodes are relinked, never copied.
Merging 3 sorted lists with 8 nodes.
Heads: 1 in a, 2 in b, 3 in c. The smallest is 1 from a, so it is unhooked from its list and linked after nothing: it becomes the merged head.
Take 1 from list a.
Heads: 6 in a, 2 in b, 3 in c. The smallest is 2 from b, so it is unhooked from its list and linked after the tail.
Take 2 from list b.
Heads: 6 in a, 5 in b, 3 in c. The smallest is 3 from c, so it is unhooked from its list and linked after the tail.
Take 3 from list c.
Heads: 6 in a, 5 in b, 4 in c. The smallest is 4 from c, so it is unhooked from its list and linked after the tail.
Take 4 from list c.
Heads: 6 in a, 5 in b, 9 in c. The smallest is 5 from b, so it is unhooked from its list and linked after the tail.
Take 5 from list b.
Heads: 6 in a, 9 in c. The smallest is 6 from a, so it is unhooked from its list and linked after the tail.
Take 6 from list a.
Heads: 8 in a, 9 in c. The smallest is 8 from a, so it is unhooked from its list and linked after the tail.
Take 8 from list a.
Only list c is left, and it is already sorted, so its remaining nodes attach as they are: 9 first.
Take 9 from list c.
One sorted list of 8 nodes, built with 8 relinks and no copies. Each pop and push costs O(log k) for k lists, so the merge is O(n log k).
Merged 8 nodes.

Remember

Compare the two heads, take the smaller, advance that list; when one list ends, attach the rest of the other.
Relink, do not copy: the merged list is made of the original nodes.
k lists: keep the current heads in a min-heap, pop the smallest, push its successor. O(n log k).

Topics covered

Where this is used

DatabasesLSM-tree compaction

RocksDB, LevelDB and Cassandra never update a row in place. They write sorted files (SSTables) and later compact several of them into one, which is a k-way merge over their keys: each file is already sorted, so only the current key of each file has to be compared, and a heap of those k keys emits the merged order. Every file is read front to back, so compaction stays sequential disk I/O and holds memory proportional to k rather than to the data.

OperationsSorting more data than fits in memory

GNU coreutils sort handles a file larger than RAM by reading it in chunks, sorting each chunk in memory, writing it to a temporary file, then merging those sorted runs. The merge is what makes it possible: it needs only one line from each run at a time, so peak memory is set by the buffer you allow it, not by the size of the input. The same shape appears in a MapReduce or Spark shuffle, where each reducer merges the sorted outputs of many mappers.

SearchSearch index segment merges

Lucene, and therefore Elasticsearch and Solr, keeps each segment's term dictionary sorted and each term's postings list in increasing document ID order. A background merge combines segments by walking their term dictionaries together: a heap holds the current term of each segment and the smallest one is emitted next, which is the k-way merge exactly. Query evaluation leans on the same sortedness, since an OR over two terms merges their postings by document ID and an AND intersects them, each in a single pass.

LanguagesTimsort's merge step

CPython's list.sort and Java's Arrays.sort for objects both use Timsort, which does not sort from scratch. It scans for runs that are already ascending or descending and then merges adjacent runs, so partly sorted input costs close to O(n). The merge has to be the stable take-the-smaller-head kind, because both languages promise that sorting on one key and then another is meaningful.

Why it works this way

Why a dummy head node?

Without it the loop needs a special case for the very first node, because there is no tail to write to yet, plus a separate variable to remember where the list started. One throwaway node removes both: the loop always writes to tail.next, and the real head is whatever ended up at dummy.next. The matching bug is returning dummy instead of dummy.next, which prefixes the answer with a stray 0.

Why <= and not < when the two heads are equal

Either comparison produces a sorted list, but <= takes from the first list on a tie, so equal values keep the order they already had. That is what makes merge sort stable, and stability is what lets you sort by one field and then another without the first sort being scrambled. Switch it to < and every run of equal keys comes out reversed.

Why a heap for k lists instead of just scanning the k heads

Scanning all k heads to find the smallest costs k comparisons per node, so the whole merge is O(nk). A heap turns that search into O(log k) because only one entry changes per step: you pop the winner and push its successor instead of rebuilding anything. Merging the lists one at a time into an accumulator is also O(nk), since the growing accumulator is walked again on every merge, but merging them pairwise in rounds like a tournament gets back to O(n log k) with no heap at all.

The k-way version is not stable unless you make it stable

A heap ordered only by value gives no promise about which of two equal values it returns first, so equal keys coming from different lists can emerge in any order. The fix is to compare on the pair (value, index of the list the node came from) so ties always resolve to the earlier list. The two-list merge gets this for free from a single <=.

Merge algorithmWikipedia
K-way merge algorithmWikipedia
listsort.txt: Tim Peters on runs and mergingCPython source · github.com
heapq.merge: k-way merge as a library callPython docs · docs.python.org
Log-structured merge-treeWikipedia