vault

K-Way Merge

16 min read

K-Way Merge

The k-way merge generalizes the two-list merge from Merge Sort: given k already-sorted input streams (lists, files, iterators) holding a total of N elements, produce a single sorted output stream in O(N log k) time and O(k) extra memory. The dominant pattern is to maintain a min-heap of size k whose elements are “the next-unread item from each input stream”; repeatedly extract the smallest and refill from whichever stream produced it. K-way merge is the engine inside external sorting (sorting data larger than RAM), inside the merge phase of distributed/sharded log processing, and inside event-driven simulations where multiple time-ordered queues are interleaved.

1. Intuition — The Coffee-Counter Analogy

Picture a coffee shop with k queues, each one already sorted by arrival time (each customer in a queue arrived after the one in front of them). The barista wants to serve all customers in true global arrival order. She can’t merge two queues at a time the way you would for k=2; she needs a way to repeatedly answer “which of the k people currently at the head of a queue arrived earliest?”

If she only ever scanned the heads of all k queues each time (linear scan), every “next” decision costs O(k), giving O(N · k) overall. The optimization is to keep a min-heap of (arrival_time, queue_id) pairs — the head element of each queue. Then “earliest of the heads” is just heap[0] in O(1), and replacing the served customer with the next one from the same queue is one heappush in O(log k). Total: N rounds of O(log k) each = O(N log k).

The “k” inside the log is what makes this a beautiful generalization. For k = 2, log k = 1, and we recover the linear-time two-list merge of Merge Sort. For k = N (each list has length 1), we degenerate into a heap sort: O(N log N).

2. Tiny Worked Example

Three sorted lists:

L0 = [1, 4, 7]
L1 = [2, 5, 8]
L2 = [3, 6, 9]

We want a single sorted output [1, 2, 3, 4, 5, 6, 7, 8, 9].

Initial heap — push the head of each list, tagged with the list index and the index within the list:

heap = [(1, 0, 0), (2, 1, 0), (3, 2, 0)]    # (value, list_idx, item_idx)

The tuple structure is critical — see §10.1 on tie-breaking. The heap orders primarily by value; ties fall back to list_idx (always distinct), which prevents Python from trying to compare items that may not be comparable.

Iteration 1. Pop (1, 0, 0) → output 1. Push next from L0: (4, 0, 1). Heap: [(2,1,0), (3,2,0), (4,0,1)].

Iteration 2. Pop (2, 1, 0) → output 2. Push next from L1: (5, 1, 1). Heap: [(3,2,0), (4,0,1), (5,1,1)].

Iteration 3. Pop (3, 2, 0) → output 3. Push next from L2: (6, 2, 1). Heap: [(4,0,1), (5,1,1), (6,2,1)].

… and so on. After 9 iterations, every element has been emitted once, in sorted order. Notice the heap stayed size 3 = k throughout — never larger.

3. Pseudocode

k_way_merge(lists):                          # lists = array of k sorted lists
    heap := empty min-heap
    for i in 0..k-1:
        if lists[i] is non-empty:
            heap.push( (lists[i][0], i, 0) ) # (value, list_idx, item_idx)
    output := empty list
    while heap is not empty:
        (value, i, j) := heap.pop_min()
        output.append(value)
        if j + 1 < length(lists[i]):
            heap.push( (lists[i][j+1], i, j+1) )
    return output

Two structural points worth noting. First, the heap is seeded with one entry per list before the main loop starts; this is what makes the “k” appear in log k — the heap is bounded by k forever. Second, every pop is followed by exactly one push from the same list the popped element came from — this preserves the invariant that the heap holds the next-unread item from each still-active list.

4. Python Implementation

The straightforward heapq version (clearest for interviews):

import heapq
 
def k_way_merge(lists):
    """Merge k sorted lists into one sorted list. O(N log k), O(k) extra."""
    heap = []
    for i, lst in enumerate(lists):
        if lst:                                    # skip empty inputs
            heapq.heappush(heap, (lst[0], i, 0))   # (value, list_idx, item_idx)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out

Note the (value, i, j) tuple. The third field j is the position within lists[i]; it would be sufficient to carry just i and look up the next item via a per-list cursor, but the tuple form is self-contained and easy to reason about. The i middle field is the unique tiebreaker that keeps the heap from ever attempting to compare two lists[i][j] values against each other when their primary keys tie (see §10.1 — this is a recurring heapq trap because heapq always compares tuples lexicographically).

4.1 Iterator-based version (handles streams, not just lists)

The list version assumes random access by index. For streams (files, generators, network sockets), use Python iterators:

import heapq
 
def k_way_merge_streams(streams):
    """Merge k sorted iterables. Streams need not fit in memory."""
    heap = []
    iters = [iter(s) for s in streams]
    for i, it in enumerate(iters):
        try:
            heapq.heappush(heap, (next(it), i))
        except StopIteration:
            pass
    while heap:
        val, i = heapq.heappop(heap)
        yield val                                  # generator output
        try:
            heapq.heappush(heap, (next(iters[i]), i))
        except StopIteration:
            pass

This is morally what the standard-library heapq.merge does (with extra optimizations); for production code, prefer it.

4.2 LeetCode 23 — linked-list flavor

import heapq
from typing import List, Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next
 
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    dummy = ListNode()
    tail = dummy
    counter = len(lists)                           # monotonic tiebreaker
    while heap:
        val, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, counter, node.next))
            counter += 1                           # ensure uniqueness across pushes
    return dummy.next

The monotonic counter is necessary because when two list nodes share a value, falling back to comparing ListNode objects raises TypeError: '<' not supported. The original list index is not a sufficient tiebreaker here either, because two pushes from the same i can both be live in the heap simultaneously if the algorithm allowed it (here it doesn’t, because of the one-pop-one-push invariant — but the monotonic counter is the bulletproof general pattern, see §10.1).

5. Complexity

Let k = number of input lists, N = total number of elements across all of them.

5.1 Time — O(N log k)

  • Initial seeding: k heap pushes, each O(log k) → O(k log k).
  • Main loop: exactly N iterations. Each iteration is one heappop (O(log k)) plus at most one heappush (O(log k)). Total: O(N log k).
  • Sum: O(k log k + N log k) = O(N log k) (since N ≥ k whenever there’s at least one element per non-empty list).

The k in log k (instead of log N) is the whole point. Sorting all N elements together with a comparison sort is O(N log N) and ignores the structure that the inputs are pre-sorted. The k-way merge exploits the per-list pre-sortedness to shrink the log factor.

5.2 Space — O(k) extra (excluding output)

The heap holds at most k entries at any time (one per still-live list). The output sequence itself is O(N), but if the output is streamed (yielded one element at a time, written to disk/network), the algorithm’s working set is O(k). This is what makes k-way merge usable for N larger than RAM — see §6.1.

5.3 Lower bound — why we can’t do better

Information-theoretically, producing a sorted output from k sorted inputs of total length N requires at least log₂(N! / (n₁! · n₂! · … · n_k!)) comparisons, where n_i is the size of list i. When all lists are roughly equal (n_i ≈ N/k), Stirling’s approximation gives this lower bound as Θ(N log k). So the k-way heap merge is asymptotically optimal in the comparison model. (Reference: Knuth TAOCP Vol. 3, §5.3.2.)

6. Use Cases

6.1 External Merge Sort (sorting data larger than RAM)

The canonical industrial use. To sort a 100 GB file with 8 GB of RAM:

  1. Run-generation phase. Read the file in 8 GB chunks; sort each chunk in memory (with Quicksort or Tim Sort); write the sorted chunk back to disk as a run. After this phase you have ~13 sorted runs on disk.
  2. Merge phase. Use a k-way merge across the 13 runs. The heap holds 13 entries (one per run); reading proceeds via buffered I/O so you read a block from each file at a time. Write the merged stream back to a single output file.

Because the merge phase only ever holds O(k) entries in memory plus per-file I/O buffers, it works regardless of total data size. This is exactly how sort(1) on Unix handles big files (it spills to /tmp once data exceeds --buffer-size), and how database engines (PostgreSQL, MySQL) implement ORDER BY for large result sets.

If k is itself huge (say, 1 million runs), the single-pass merge becomes I/O-bound on disk seeks. The standard solution is multi-pass merging: do √k runs of √k-way merges in parallel, then merge their outputs. Knuth §5.4 covers the optimal merge-pattern theory (the “Huffman-tree merge order” — see Huffman Coding).

6.2 Multi-Shard Log Merging

A typical distributed system (Kafka, Elasticsearch, Spanner) stores a logical log split across many shards, each shard internally ordered by timestamp. To replay events globally in time order — for analytics, audit, or replication — you k-way-merge the shards. The “lists” are the shard iterators, and the “values” are events keyed by (timestamp, shard_id) to deterministically break ties.

Latency-sensitive systems use a time-bounded merge that emits an event only after waiting long enough that no shard could plausibly produce an earlier one (a watermark, in stream-processing parlance). Apache Flink, Kafka Streams, and Google Dataflow all wrap k-way merging in watermark machinery for this purpose.

6.3 Priority-Queue-Driven Event Simulation

Discrete-event simulators (network simulators, game engines, hardware simulators) need to process events in time order. When events come from multiple independent sources — say, traffic generators on different network nodes — each source produces events in its own time order, so the global event ordering is a k-way merge. The heap in this case is the event queue; each pop fires the next event, which may schedule new events into the heap.

6.4 Database Range Scans Across Sharded Indexes

A B-tree index range-scan returns rows in order of the indexed column. When the index is sharded across nodes (each shard has its own B-tree), a query like SELECT … ORDER BY ts LIMIT 100 translates to a k-way merge of the per-shard scans, with early termination after 100 rows. Modern column stores (Snowflake, ClickHouse) explicitly use this pattern.

6.5 Smallest-K-in-N-Sorted-Lists (LC 378, LC 632)

LC 378 (kth-smallest in a sorted matrix) and LC 632 (smallest range covering elements from k lists) are both flavor-variants. For LC 378, treat each row as a sorted list and run the merge for k pops. For LC 632, the heap holds one element per list, and you track the running max while popping; whenever you pop, you’ve found the candidate range [min_in_heap, current_max] — minimize that across all states.

7. Variants

7.1 Tournament Tree (Loser Tree)

Knuth’s preferred external-sort merge primitive (TAOCP §5.4.1). Instead of a heap, use a complete binary tree where each internal node holds the loser of the comparison between its subtree’s two streams; the global winner sits “above” the root. After emitting the winner, we replay only the path from the winning leaf to the root — log₂(k) comparisons, but with a constant factor that’s roughly half the heap’s because we don’t sift-down from the top each time. Used in classical tape-sort implementations; rarely beats a binary heap on modern CPUs because the cache behavior of a flat array beats pointer-chased trees.

7.2 Pairwise (Divide-and-Conquer) K-Merge

Repeatedly merge pairs of lists: round 1 produces ⌈k/2⌉ lists, round 2 produces ⌈k/4⌉, etc. After log₂(k) rounds, one list remains. Each round processes all N elements. Total: O(N log k) — same asymptotic cost as the heap version. Often appears as the “alternative implementation” for LC 23. Slightly better cache behavior in some microbenchmarks; worse memory profile (each round materializes all N elements).

7.3 Polyphase Merge

When the number of available scratch tapes/files is fixed (say, 3) but you have many runs to merge, the polyphase merge interleaves merging and run-redistribution to minimize total I/O. Pure history at this point — relevant when reading old systems papers, but no production system uses tape constraints anymore.

7.4 Parallel K-Way Merge

For multicore implementation, partition the value space into p ranges (one per core); each core merges only its portion of each input stream. Tricky load-balancing — the canonical reference is Cole’s “Parallel merge sort” (1988). Most modern systems (GNU parallel, Spark) implement merging via shuffle-then-sort instead.

9. Pitfalls

9.1 Heap Tie-Breaking — The TypeError Trap

When two heap entries have the same primary key, Python falls back to comparing the second tuple element, then the third, etc. If the second element is a ListNode, a dict, or any non-comparable type, you get TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'. The fix is to always include a provably unique, totally-ordered tiebreaker (the list index i, or a monotonic counter) before any potentially-uncomparable payload. This is the single most common bug in interview k-way-merge implementations.

9.2 heapq Is Min-Heap by Default

Python’s heapq primitives (heappush/heappop/heapify) build a min-heap; for decades there was no max-heap API at all. Python 3.14 added explicit *_max variants (heapify_max, heappush_max, heappop_max, heapreplace_max, heappushpop_max), but for portability and for the common case the standard idiom is still: for a k-way descending merge (largest first), negate values on push and on read — heapq.heappush(heap, (-val, i, j)). The negation trick fails for non-numeric values; for those, wrap in a class with __lt__ reversed (or use the tuple-with-negative-sort-key pattern). For lazy descending merges, heapq.merge(..., reverse=True) works directly on inputs sorted largest-to-smallest. See Binary Heap §5.

9.3 Forgetting to Skip Empty Lists at Init

If lists[i] is empty and you blindly push lists[i][0], you get IndexError. Always guard with if lst: (or a try/except StopIteration for iterators).

9.4 Not Re-Pushing After Popping

Every pop must be followed by an attempt to push the next item from the same list. Forgetting this leaves only one element per list ever appearing in the output — an extremely silent bug because the output starts correct (the first k items are right).

9.5 Re-Sorting Each Loop Iteration

A common naive “k-way merge” answer is to put all candidate heads in a list and call min(...) each iteration — this is O(N · k), not O(N log k). The heap is the entire performance argument; do not regress to a linear scan.

9.6 Stable-Order Loss When Using Negation

Negating values for max-heap behavior reverses ordering — including tiebreaker order. If you need stability among equal keys, the negation trick combined with an ascending counter produces reverse stability. Use a class with reversed __lt__ instead, or negate the counter as well.

9.7 Memory Blowup From Eager List Materialization

If you eagerly materialize all N items into the heap up front (instead of streaming one-per-list), memory becomes O(N) and the algorithm is just heap-sort with extra steps. The whole point is O(k) working set; preserve it.

10. Diagram — The Heap as a Front of K Cursors

flowchart LR
    subgraph Inputs[k sorted input lists]
        L0["L0: 1, 4, 7"]
        L1["L1: 2, 5, 8"]
        L2["L2: 3, 6, 9"]
    end
    subgraph Heap[Min-heap size k - one head per list]
        H["heap = [ 1,L0  2,L1  3,L2 ]"]
    end
    L0 -- "head pointer" --> H
    L1 -- "head pointer" --> H
    L2 -- "head pointer" --> H
    H -- "pop smallest, advance that list's head" --> Out["Output: 1, 2, 3, 4, ..."]

What this diagram shows. The heap is conceptually a frontier — the leading edge of k parallel cursors marching through the k input lists. At each step, the smallest of the k frontier values is the next-correct global output, and only the cursor that produced it advances (the other k-1 are still in the right place). The heap merely provides O(log k) access to “smallest of the frontier”; the algorithmic invariant is the frontier itself, which is what makes the working set O(k) rather than O(N). This is also why the algorithm streams: at no point does it need to materialize more than k items.

11. Common Interview Problems

LeetCode #TitleTwist
23Merge k Sorted ListsPlain vanilla — linked-list flavor
378Kth Smallest Element in a Sorted MatrixEach row = list; pop k times
632Smallest Range Covering Elements from K ListsTrack max_in_heap while merging
264 / 313Ugly Number II / Super Ugly NumberMerge streams 2x, 3x, 5x
373Find K Pairs with Smallest SumsHeap of pair-streams
786K-th Smallest Prime FractionHeap of fraction-streams
1675Minimize Deviation in ArrayVariant: running max/min via heap

Beyond LeetCode, the same pattern is the expected answer in system-design rounds for external merge sort (run-generation + k-way merge phase, §6.1) and for “merge sorted event streams from N microservices/shards” (the iterator-based variant of §4.1).

12. Open Questions

  • When does a tournament/loser tree beat a binary heap in practice on modern hardware? Most published microbenchmarks find them within 10% of each other; the binary heap’s cache locality wins on small k.
  • For very large k (say, k > 10⁵), is the single-pass merge ever I/O-bound enough that two-pass merges (√k by √k) win? Answer is yes for spinning disks; SSDs largely erase the seek-cost gap, but the read-buffer-fit constraint (see the callout above) still forces a bounded fan-in. The specific crossover figure is engine-dependent — verify against the target engine’s spill/merge-order configuration rather than trusting a single round number.

Uncertain uncertain

Verify: the specific k threshold at which a two-pass (√k × √k) merge beats a single-pass merge on SSD-backed storage. Reason: this is governed by the merge fan-in vs. per-stream read-buffer size trade-off (each open run needs a sequential read buffer; once k buffers no longer fit in the sort memory budget the single pass thrashes), which is workload- and engine-specific — no clean published rule covers it, and the §6.1/§7.2 figures here (“k > 100” for Spark/Snowflake) are folklore, not a cited benchmark. To resolve: measure on the target storage layer, or cite the specific engine’s documented sort_buffer/spill-fan-in defaults (e.g. PostgreSQL’s maintenance_work_mem-derived merge order).

13. See Also

Graph View

Backlinks