Merge K Sorted Lists, in depth: the min-heap merge, divide and conquer, and k-way merging in real systems

The problem, precisely

Input: k sorted sequences L0 ... Lk-1 with lengths summing to N. Some may be empty. Output: all N elements in non-decreasing order. For linked lists, the usual form of the question, you may relink the existing nodes rather than allocate new ones, so the extra space we care about is the bookkeeping, not the output.

Two quantities drive every cost below: N, the total work you cannot avoid because every element must be output once, and k, the number of candidates you must choose between at each step. Good algorithms make the per-element cost depend on k, not on N.

Three slower answers and why they lose

Concatenate and sort. Copy everything into an array and sort it: O(N log N) time and O(N) extra space. It ignores the fact that the inputs are already sorted. When k is small relative to N, log k is much smaller than log N, and that is the gap the better algorithms exploit. It is still a reasonable baseline for small inputs, because library sorts are heavily tuned and some, such as TimSort, detect pre-sorted runs.

Scan all heads every step. Look at all k heads, take the minimum, advance that list. Each output costs O(k), so the total is O(Nk). Fine for k of 2 or 3, terrible for k of 1,000.

Merge one list at a time. Merge L0 with L1, then the result with L2, and so on. The accumulated result is re-walked at every step. With k lists of n elements each, the merges cost roughly 2n + 3n + ... + kn, which is O(k²n), or O(kN). The early elements are copied over and over.

All three waste work in the same way: they repeatedly compare elements whose relative order is already known. The heap answers the only question that matters, which head is smallest, without rescanning.

The min-heap algorithm

Put the head of every non-empty list into a min-heap ordered by value. Repeat until the heap is empty: pop the minimum, append it to the output, and if that element has a successor in its own list, push the successor.

Why it is correct: the heap always contains exactly the smallest unconsumed element of every non-empty list. Every unconsumed element is greater than or equal to the head of its own list, so the heap's minimum is less than or equal to every unconsumed element anywhere, and it is therefore the correct next output. Popping it and pushing its successor restores the invariant.

Why it costs O(N log k): the heap never holds more than k entries, so each push and pop costs O(log k). Every element is pushed once and popped once, giving 2N heap operations. Building the initial heap costs O(k). Extra space is O(k) for the heap. A comparison-based merge cannot do asymptotically better in general, because the number of ways to interleave k sorted lists implies a lower bound of roughly N log k comparisons when the lists have similar lengths.

import java.util.PriorityQueue;

final class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

final class MergeK {
    static ListNode mergeKLists(ListNode[] lists) {
        // Integer.compare, not a.val - b.val: subtraction overflows for large magnitudes
        // (Integer.MIN_VALUE - 1 wraps to a positive number) and silently mis-orders.
        PriorityQueue<ListNode> heap =
            new PriorityQueue<>(Math.max(1, lists.length), (a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) {
            if (head != null) heap.offer(head);         // skip empty lists
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode min = heap.poll();                  // O(log k)
            tail.next = min;
            tail = min;
            if (min.next != null) heap.offer(min.next);  // O(log k)
        }
        tail.next = null;                                // defensive: the last node already ends a list
        return dummy.next;
    }
}

Three details in that code matter. The comparator uses Integer.compare: the tempting (a, b) -> a.val - b.val overflows when values are far apart, for example a large positive minus a large negative, and the wrapped result reverses the order without any error. Empty lists are skipped at insertion, so null never reaches the comparator. And PriorityQueue requires an initial capacity of at least 1, hence the Math.max.

Worked example: tracing three lists

Take L0 = 1, 4, 7, L1 = 2, 5, 8 and L2 = 3, 6, 9. The heap starts as {1 from L0, 2 from L1, 3 from L2}.

Nine pops and six pushes after the three initial insertions, and the heap never exceeded three entries. Now imagine the same lists with k = 10,000 and a million elements each: the heap still has at most 10,000 entries, and each step costs about log2(10,000), around 13 levels, rather than 10,000 comparisons for the scanning approach.

Python: ties, laziness and the standard library

In Python the same algorithm needs one extra field. heapq compares tuples element by element, so if two entries have equal values it falls through to comparing the next field. Comparing two iterators or two node objects raises TypeError. Putting the list index second guarantees every tuple is distinct before that point and, as a side effect, makes the merge stable: equal values come out in the order of their input lists.

import heapq

def merge_k(iterables):
    """Merge already-sorted iterables lazily. Yields values in ascending order.

    Entries are (value, index, iterator). The index breaks ties so Python never has to
    compare two iterators (TypeError), and it makes equal values come out in input order.
    """
    heap = []
    for i, it in enumerate(map(iter, iterables)):
        for first in it:                 # take the first element, if any
            heap.append((first, i, it))
            break
    heapq.heapify(heap)                  # O(k)
    while heap:
        value, i, it = heap[0]
        yield value
        nxt = next(it, _END)
        if nxt is _END:
            heapq.heappop(heap)          # this input is exhausted
        else:
            heapq.heapreplace(heap, (nxt, i, it))   # pop + push in one sift

_END = object()

# The standard library already provides this, including key= and reverse=:
#   list(heapq.merge([1, 4, 7], [2, 5, 8], [3, 6, 9]))  ->  [1, 2, ..., 9]

This version is a generator, so it works on inputs that do not fit in memory, such as lines read from many sorted files, and produces output as soon as the first element is known. heapreplace pops and pushes in a single sift, which is cheaper than two separate operations. In production Python, prefer heapq.merge, which does the same thing and supports key and reverse.

Divide and conquer: same bound, no heap

Merging pairs of lists in rounds, like the merge step of merge sort, achieves the same bound without a priority queue. Round one merges k lists into k/2, round two into k/4, and after log k rounds one list remains. Every element takes part in exactly one two-way merge per round, so each round costs O(N) and the total is O(N log k).

static ListNode mergeKDivide(ListNode[] lists) {
    if (lists.length == 0) return null;
    // Bottom-up: merge pairs at distance 1, then 2, then 4 ... in place.
    for (int step = 1; step < lists.length; step *= 2) {
        for (int i = 0; i + step < lists.length; i += 2 * step) {
            lists[i] = mergeTwo(lists[i], lists[i + step]);
        }
    }
    return lists[0];
}

static ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }   // <= keeps it stable
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

The bottom-up loop needs no recursion stack, and mergeTwo uses <= so ties prefer the earlier list. The trade-off is shape: this version needs every list available up front and finishes rounds before producing the first output, so it suits in-memory batch merging. The heap version is incremental and works on streams. Which is faster in practice depends on data size, element type and language runtime; the asymptotic cost is the same, so measure on your own data before choosing for speed. The general pattern is covered in divide and conquer.

Edge cases checklist

• k = 0 or all lists empty: return an empty result; make sure the heap or array constructor accepts that.
• Null or empty entries mixed in: filter them before the heap, never inside the comparator.
• Duplicates: equal values are fine; decide whether you need stability and break ties by list index if so.
• Very uneven lengths: one list of a million and 999 lists of one element still runs in O(N log k), and the heap shrinks quickly as the short lists drain.
• Unsorted input: the algorithm does not check its precondition and will emit unsorted output. Validate inputs from untrusted sources, or assert ordering as you consume each list.
• Descending order: use a max-heap or a reversed comparator; in Python, heapq.merge(..., reverse=True) expects each input sorted descending.

K-way merging in real systems

External sorting. To sort data larger than memory, read memory-sized chunks, sort each, and write them as sorted runs. Then merge all runs in one k-way pass with one read buffer per run and a heap over the buffered heads. The design question is buffer size: larger buffers mean fewer, more sequential disk reads, but memory divided by buffer size caps k. When there are more runs than buffers, merge in several passes.

LSM-tree compaction. Storage engines like Cassandra's and RocksDB's write sorted files and later merge them. Compaction is a k-way merge over sorted file iterators with one twist: when the same key appears in several inputs, the newest version wins and the others are dropped. See LSM trees for how that fits into the write path.

Scatter-gather queries. A query sent to many shards gets back k sorted result pages. A heap merge produces the global order, and if you only need the first m results, you can stop after m pops, which costs O(k + m log k) instead of the whole merge, the same idea behind top-k selection.

In systems, two practical failures dominate. A slow or stalled input blocks the whole merge, because the heap cannot emit anything greater than a head it has not seen yet, so streaming merges need timeouts or watermarks. And one iterator throwing mid-merge leaves the output partially written, so writers should emit to a temporary file and rename on success.

Choosing an approach

What to do next

1. Implement the heap version from memory in your main language, with the tie-breaking index and an overflow-safe comparator, and test it on the trace above.
2. Add tests for k = 0, all-empty lists, duplicates across lists, one very long list among many short ones, and extreme values such as the minimum and maximum integers.
3. Implement the bottom-up pairwise merge and compare both against concatenate-and-sort on your own data sizes before deciding which is fastest.
4. Rewrite the heap version as a lazy iterator over files, and stop it early to return only the first m results.
5. Read how your database's compaction or your query engine's sort-merge join uses a k-way merge, and identify what happens there when one input is slow or fails.