K-way Merge: The Pattern for Sorted Streams

TL;DR: When a problem hands you multiple already-sorted inputs (k lists, k arrays, the rows of a sorted matrix), the next element of the merged output must be one of the k current heads, so you keep exactly those k candidates in a min-heap: pop the overall smallest, push its successor from the same source, repeat. That "frontier of k heads" insight merges N total elements in O(N log k) with O(k) memory, and it solves Merge k Sorted Lists, Kth Smallest in a Sorted Matrix, Find K Pairs with Smallest Sums, and the Smallest Range problem with one template. It's Top-K's sibling: same heap, opposite job. There, the heap selected winners; here, it weaves streams.

This is the seventh deep dive in our pattern series (the full map lives in the hub), and it picks up exactly where Top 'K' Elements left off: Merge k Sorted Lists was that post's boss fight, and it's this post's front door. K-way Merge is the smallest pattern in the series by concept count (one insight, one template), which is precisely why interviewers like it: there's nowhere to hide behind memorization, and the wrong-tool versions (concatenate and sort, or pairwise merging) expose themselves in the first minute.

The tell: how to recognize a K-way Merge problem

• "merge k sorted lists / arrays / streams"
• "kth smallest element across / in a row-and-column-sorted matrix"
• "find the smallest range that includes at least one number from each of k lists"
• "k pairs with the smallest sums" (two sorted arrays, implicit lists)
• any "combine these sorted feeds" system flavor: merging time-sorted logs, event streams, leaderboards

The tell is sortedness you were given, in pieces. One sorted input suggests two pointers or binary search; several sorted inputs is this pattern's exclusive territory. And the reflex to interrogate: if you're about to concatenate everything and sort, you're about to throw away the very property the problem handed you.

The one insight the whole pattern rests on

Say this in the interview, because it is the pattern: the smallest remaining element overall must be the head of one of the k sources, because everything behind a head is bigger than that head. So you never need to consider more than k candidates at once. Keep those k heads in a min-heap: the root is the next output element, and when you pop it, its successor from the same source becomes a candidate. Every element enters the heap exactly once and leaves once, so N total elements cost O(N log k), with the heap never holding more than k items.

That frontier idea is the entire pattern. Everything below is bookkeeping.

The template

Merge k Sorted Lists (LeetCode 23), the canonical form:

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # (key, tiebreak, payload)
    dummy = tail = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)              # smallest head overall
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # successor joins
    return dummy.next

Note the middle element of the tuple: the source index i. It's not decoration. When two heads tie on value, Python compares the next tuple field, and comparing two ListNode objects crashes. The index breaks ties cheaply and never collides. This one line is the most common K-way Merge bug in interviews, and including it unprompted is a fluency signal.

The variations, and what each one adds

• Kth Smallest Element in a Sorted Matrix (LeetCode 378): each row is a sorted list; run the template and pop k times. The heap holds at most min(k, rows) heads. (There's also a binary-search-on-value solution, which makes this problem a favorite "compare two approaches" prompt; knowing both and their trade-offs is the senior answer.)
• Find K Pairs with Smallest Sums (LeetCode 373): nothing looks sorted until you see the implicit lists: for each element of array A, the pairs (A[i], B[0]), (A[i], B[1]), ... form a sorted stream. The mapping is the hard part; afterward it's the template verbatim. This is the pattern's best recognition test.
• Smallest Range Covering Elements from K Lists (LeetCode 632): the boss fight. Keep one head per list in the heap (the range's minimum is the root) while separately tracking the running maximum of heap contents; each pop-and-advance narrows or shifts the candidate range. It composes the frontier with a running aggregate, and explaining why the range's minimum must be a heap root is the graded moment.
• Merge Two Sorted Lists / Arrays: k = 2, where the heap degenerates to a comparison, which is exactly the two-sequence template from two pointers. Patterns nest: K-way Merge is two pointers generalized past two.

Want each variation taught step by step? The K-way Merge chapter of Grokking the Coding Interview builds from two-list merging through Smallest Range with visual heap traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The three mistakes that sink candidates

1. Concatenate-and-sort. O(N log N), ignores the given sortedness, and burns the interview's actual question. It's a fine 15-second baseline to mention ("brute force: flatten and sort, N log N; we can do better because the inputs are sorted"), and a poor thing to code.

2. Heaping everything. Pushing all N elements into one heap "works" at O(N log N) time and O(N) space, but the frontier version's whole point is the heap never exceeds k. If your heap can hold more than k items, you've rebuilt mistake #1 with extra steps. (Same failure shape as heaping all n in Top-K.)

3. The tuple-comparison crash. Equal keys make the heap compare payloads, and payloads (list nodes, custom objects) usually aren't comparable. The source-index tiebreaker fixes it structurally. If your language's priority queue takes a comparator instead, define it explicitly; "it worked on the sample" is how this bug reaches the interview's final minutes.

Practice ladder

1. Merge Two Sorted Lists (E): the k = 2 degenerate case; notice it's just two pointers.
2. Merge k Sorted Lists (H): the canonical template, tiebreaker included; rehearse the frontier argument aloud.
3. Kth Smallest Element in a Sorted Matrix (M): rows as lists; be ready to discuss the binary-search alternative.
4. Find K Pairs with Smallest Sums (M): the implicit-lists mapping; the recognition test.
5. Smallest Range Covering Elements from K Lists (H): frontier plus running max; the boss fight.

Then write the tell in your own words ("I should suspect K-way Merge when ___") and move on. Five problems with the frontier argument owned beats twenty without it, as ever.

The takeaway

One insight (the next element must be a head), one structure (a heap holding exactly the k heads), one complexity story (N log k, memory k), one bug to pre-empt (the tiebreaker). K-way Merge is the cleanest demonstration in the series that patterns are small: what interviewers are testing isn't whether you can hold a big algorithm in your head, it's whether you see the frontier in the first two minutes. Next in the series: Modified Binary Search, including the disguise the hub's live diagnosis already teased: binary searching the answer itself.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79. Short on time? Grokking 75 covers the essential merge problems in its 6-week plan.

FAQs

What is the K-way merge pattern in simple terms? Given k sorted inputs, keep just their current first elements (the "heads") in a min-heap. The heap's root is always the next element of the fully merged output; pop it and push that source's next element. N total elements merge in O(N log k) time with only O(k) extra memory.

Why is K-way merge O(N log k) and not O(N log N)? Because the heap never contains more than k items, every push and pop costs O(log k), and each of the N elements is pushed and popped exactly once. Flattening everything into one big sort (or one big heap) is what costs O(N log N), and it ignores the sortedness the problem gave you.

How is K-way Merge different from Top-K? Same data structure, opposite job. Top-K uses a size-k heap as a filter (keep the k best, discard the rest); K-way Merge uses a size-k heap as a frontier (always emit the global next, never discard anything). The tells differ too: Top-K's input is unsorted with a k in the ask; K-way Merge's input is pre-sorted in pieces.

Why do I need the index in the heap tuple for Merge k Sorted Lists? When two nodes have equal values, the heap breaks the tie by comparing the tuple's next field, and list nodes aren't comparable, which crashes at runtime (and only on inputs with duplicates, so it survives light testing). A monotonically assigned source index makes every tuple unique before comparison ever reaches the payload.

Is K-way Merge actually asked in interviews? Regularly: Merge k Sorted Lists is a top-frequency hard at Meta, Amazon, and Google, Kth Smallest in a Sorted Matrix is a standard "compare two approaches" prompt, and the merging-sorted-logs framing shows up in practical rounds. It's also quietly the algorithm inside external merge sort, so infrastructure-flavored loops treat it as real-world knowledge, not trivia.