Merge K Sorted Lists: Min-Heap vs Divide and Conquer

Merging two sorted lists is a warm-up. Merging k of them is where a question starts to separate solutions that work from solutions that scale. There are three natural answers, and two of them are O(n log k). The third looks just as reasonable and is O(n × k).

This article covers the min-heap merge, the pairwise merge, the reason the obvious loop is slow, and the one Python detail that breaks the heap version on linked lists.

The problem it solves

You have k lists, each already sorted, holding n values between them. Produce one sorted list.

The shape is everywhere once you look: combining sorted runs in an external sort, merging per-shard results that each come back ordered, interleaving several time-ordered logs into one timeline. In every case the inputs are too valuable to throw away — each is sorted already — and sorting the concatenation from scratch ignores that work.

The intuition

At any moment, the next value of the output must be the front of some list. Nothing behind a front can beat it, because each list is sorted. So the question "what comes next?" only ever needs to look at k candidates.

A min-heap of the k fronts answers it in O(log k). Pop the smallest, append it to the output, and push the value that was behind it in the same list. The heap never holds more than k entries, however long the lists are.

The divide-and-conquer answer uses only the two-list merge. Pair the lists up and merge each pair; k lists become k / 2. Repeat. After log k rounds one list is left, and each round touches every value once.

The slow answer also uses only the two-list merge, but merges the lists into a running result one at a time. The trouble is that the running result is re-copied on every step: the first list's values are moved k times, the second's k - 1 times, and so on.

Watch it run

Three sorted lanes feed a heap that holds one value per lane. Each step pops the root to the output strip and pulls the next value from the lane it came from — watch the heap refill from exactly that lane, and never grow past three entries.

The code

The heap merge, the two-list merge both other strategies are built on, and a count of how many values each strategy copies:

import heapq

def merge_k_heap(lists):
    heap = [(rows[0], i, 0) for i, rows in enumerate(lists) if rows]
    heapq.heapify(heap)                         # one head per list, nothing more
    out = []
    while heap:
        value, i, pos = heapq.heappop(heap)
        out.append(value)
        if pos + 1 < len(lists[i]):             # the list it came from steps forward
            heapq.heappush(heap, (lists[i][pos + 1], i, pos + 1))
    return out

def merge_two(a, b, moved):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out += a[i:] + b[j:]
    moved[0] += len(out)
    return out

def merge_k_one_by_one(lists, moved):
    out = []
    for rows in lists:
        out = merge_two(out, rows, moved)       # the growing result is re-copied every time
    return out

def merge_k_pairs(lists, moved):
    lists = [rows for rows in lists]
    while len(lists) > 1:                       # halve the number of lists per round
        lists = [merge_two(lists[k], lists[k + 1], moved) if k + 1 < len(lists)
                 else lists[k] for k in range(0, len(lists), 2)]
    return lists[0] if lists else []

print(merge_k_heap([[1, 6, 9], [2, 4], [3, 8]]))    # [1, 2, 3, 4, 6, 8, 9]

lists = [list(range(i, 64_000, 64)) for i in range(64)]   # k = 64 lists of 1,000
for merge in (merge_k_one_by_one, merge_k_pairs):
    moved = [0]
    merge(lists, moved)
    print(merge.__name__, moved[0])
# merge_k_one_by_one 2080000
# merge_k_pairs 384000

With 64 lists of 1,000 values, merging one at a time copies 2,080,000 values. Pairing copies 384,000: 64,000 values times six rounds, and six is log2 64. The heap version moves each of the 64,000 values exactly once, paying O(log k) for the heap operation instead.

All three are checked against the laziest possible answer — pour everything into one list and sort it — on thousands of random inputs, including empty lists and duplicates:

import random

random.seed(12)
ok = True
for _ in range(3000):
    k = random.randint(0, 7)
    lists = [sorted(random.randint(0, 9) for _ in range(random.randint(0, 6)))
             for _ in range(k)]
    expected = sorted(v for rows in lists for v in rows)   # brute force: pool and sort
    ok &= merge_k_heap(lists) == expected
    ok &= merge_k_pairs(lists, [0]) == expected == merge_k_one_by_one(lists, [0])
print(ok)                                       # True

The complexity

• Heap: n pops and at most n pushes on a heap of size k. O(n log k) time, O(k) extra memory besides the output.
• Pairwise: log k rounds, each copying all n values. O(n log k) time. On arrays it needs O(n) scratch space per round; on linked lists the merge can splice nodes and use O(1).
• One by one: the j-th merge copies everything merged so far. With equal lists of length n / k that is n / k × (1 + 2 + … + k), about n × k / 2. O(n × k).
• Pool and sort: O(n log n). Fine in practice when k is close to n, but it throws away the sortedness you were given.

When k is small, log k is nearly a constant and the merge is effectively linear. It is one reason external sorts merge many runs in a single pass rather than two at a time: fewer passes over the data.

Where it goes wrong

• Pushing bare nodes into the heap. In Python, heapq compares whole tuples. If two linked-list nodes carry the same value, it moves on to compare the nodes themselves, and nodes do not support <.
• Pushing every value up front. Heapifying all n values works, but the heap is size n and the merge becomes O(n log n). Only the fronts belong in the heap.
• Forgetting empty lists. An empty input list has no front. Skip it when seeding the heap, or reading its first element fails.
• Advancing the wrong list. After a pop, push the successor from the list that value came from — which is why each heap entry carries its list index.

The first one is worth seeing, because small hand-made examples rarely contain a repeated value:

import heapq

class Node:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

heap = []
heapq.heappush(heap, (5, Node(5)))
try:
    heapq.heappush(heap, (5, Node(5)))          # equal values: Python compares the nodes
except TypeError as error:
    print(error)                                # '<' not supported between instances of 'Node' and 'Node'
heap = []
for i, node in enumerate([Node(5), Node(5)]):
    heapq.heappush(heap, (node.val, i, node))   # the index settles every tie
print(len(heap))                                # 2

A unique tiebreaker between the value and the node — the list index, or a running counter — means the comparison never reaches the node.

The two-list building block is its own lesson: merge two sorted lists.

How to say it in an interview

"The next output value is always one of the k list fronts, so I keep just those in a min-heap. I pop the smallest, append it, and push the next value from the same list. Every value is pushed and popped once on a heap of size k, so it's O(n log k) time and O(k) extra space. The alternative is pairwise merging — log k rounds of linear merges, same bound. Merging into one running list is O(n × k) because early values get copied over and over."

If the lists are linked lists, mention the tiebreaker before you write the push. It is a bug that stays hidden until two lists share a value.