Lesson 21 · Intermediate

K-way merge

📖 Walk me through it — plain English

The job: you have k separate lists that are each already sorted (smallest to largest), and you want to combine them into one big sorted list. The lazy way is to dump everything into one pile and sort the whole thing — but that ignores a free gift: each list is already in order. The smallest number still left anywhere must be sitting at the front of one of the lists. So we never need to look deep inside any list; we only ever compare the current front elements. The catch is finding which front is smallest, fast.

A min-heap is the right tool. Think of it as a magic bucket: you toss numbers in, and it always hands back the smallest one on request, cheaply (cost O(log k) — meaning the work grows only with the logarithm of how many items are in the bucket, so it stays tiny even as k grows). We keep at most one "front" element per list in the bucket. Repeat: take the smallest out, write it to the answer, then refill the bucket with the next element from the very same list that number came from.

Everyday analogy: imagine k card dealers, each holding a stack of cards sorted with the smallest on top. To build one sorted pile, you keep glancing at the top card of every dealer, grab the globally smallest one, and place it down. The dealer you just took from flips their next card up. You repeat until all dealers are empty. The min-heap is just an efficient way to "glance" — instead of eyeballing all k tops every time, the heap tells you the smallest instantly.

Each heap entry is a little tuple (value, listIndex, elemIndex): the number itself, which list it came from, and its position in that list. We carry listIndex so that after popping we know exactly which list to pull the next card from — and as a bonus it breaks ties cleanly so the heap never has to compare anything weird.

Our three sorted lists. L0 = [1, 4, 5], L1 = [1, 3, 4], L2 = [2, 6]. We only ever look at the front (highlighted) of each.

Step 1 · Seed the heap with each list's first element. The heap now holds these three entries (shown as their values). Output so far: empty.

Step 2 · Pop the smallest: it is 1 from L0 (tuple (1,0,0)). Write it to the output. Then push L0's next element, 4. Heap now = {1 from L1, 2 from L2, 4 from L0}.

Step 3 · Pop the smallest again: 1 from L1 (tuple (1,1,0)). Write it. Push L1's next element, 3. Heap now = {2 from L2, 3 from L1, 4 from L0}. Output so far: [1, 1].

Step 4 · Pop 2 from L2, write it, push L2's next element 6. Heap = {3 from L1, 4 from L0, 6 from L2}. Output so far: [1, 1, 2].

Keep going — pop 3, then 4 (from L0), then 4 (from L1), then 5, then 6 — until the heap empties. The output comes out fully sorted:

Why it works: at every step the true smallest remaining number must be at the front of some list, and all those fronts are exactly what the heap holds — so popping the heap's minimum always grabs the correct next number. Why the speed: there are N numbers total, and each one gets pushed into the heap once and popped once. The heap never holds more than k items (one live front per list), so each push/pop costs O(log k). Multiply: N elements times log k per operation gives O(N log k) time, plus O(k) extra space for the heap. When k is much smaller than N, that beats the dump-and-sort cost of O(N log N).

You already know how to merge two sorted lists: walk a pointer down each, repeatedly take the smaller head. K-way merge is the same idea scaled to k sorted inputs at once. The naive move — concatenate everything and sort — throws away the fact that each input is already sorted and costs O(N log N). We can do better. The bottleneck of merging is just "which of the current heads is smallest?", and a min-heap answers exactly that in O(log k) instead of an O(k) linear scan. So we keep a heap of size at most k — one live candidate per list. Concretely, seed it with the first element of every list as a tuple (value, listIndex, elemIndex). Then loop: pop the smallest, append its value to the output, and push the next element from that same list. Each of the N elements is pushed and popped once, each op is O(log k), so the whole merge is O(N log k) time and O(k) extra space. A clean anchor: merging k sorted lists into one. There is also a pointer-free framing — pairwise divide-and-conquer: merge the lists two at a time (list 0 with 1, 2 with 3, ...), halving the count each round. Across log k rounds you touch all N elements per round, which is also O(N log k) — same asymptotics, no heap required.

Trigger signals

"Merge k sorted lists / arrays / streams" into one sorted output
kth smallest across sorted rows or sorted lists
"Smallest range" that covers at least one element from each of k lists
Many already-sorted sources, and you'd otherwise re-sort the union

Canonical problems

Merge k Sorted Lists — heap of list heads, O(N log k)
Kth Smallest Element in a Sorted Matrix — rows are k sorted lists; pop k times
Smallest Range Covering Elements from K Lists — heap holds one per list; range = (max seen, heap min)

Template — Merge k sorted lists (min-heap)

import heapq

def merge_k(lists):
    # lists: list of sorted lists, e.g. [[1,4,5],[1,3,4],[2,6]]
    heap = []
    for li, lst in enumerate(lists):
        if lst:                                  # skip empty lists
            heapq.heappush(heap, (lst[0], li, 0))  # (value, listIndex, elemIndex)
    out = []
    while heap:
        val, li, ei = heapq.heappop(heap)        # smallest current head
        out.append(val)
        if ei + 1 < len(lists[li]):             # advance THIS list's pointer
            nxt = lists[li][ei + 1]
            heapq.heappush(heap, (nxt, li, ei + 1))
    return out
    # N total elements, heap size <= k  ->  O(N log k) time, O(k) space

// TS has no built-in heap. Sketch a MinHeap keyed by value;
// entries are [value, listIndex, elemIndex].
type Entry = [number, number, number];

function mergeK(lists: number[][]): number[] {
  const heap = new MinHeap<Entry>((a, b) => a[0] - b[0]);
  lists.forEach((lst, li) => {
    if (lst.length) heap.push([lst[0], li, 0]);  // skip empty
  });
  const out: number[] = [];
  while (heap.size > 0) {
    const [val, li, ei] = heap.pop()!;       // smallest head
    out.push(val);
    if (ei + 1 < lists[li].length)         // advance this list
      heap.push([lists[li][ei + 1], li, ei + 1]);
  }
  return out;                                  // O(N log k)
}

Key trick — why the listIndex is in the tuple

Python's heap compares tuples lexicographically: it only looks past value when two values tie. If your payload is a linked-list node (as in Merge k Sorted Lists), comparing nodes raises TypeError: '<' not supported. Putting the unique listIndex as the second tuple element guarantees ties resolve there and the node is never compared. Each list has at most one live heap entry, so the listIndex is unique among entries — a perfect tiebreaker.

Complexity & gotchas

Time O(N log k), space O(k) for the heap — N = total elements, k = number of lists. Beats concat-then-sort's O(N log N) when k << N.
Always include the listIndex (and/or a counter) in the heap tuple as a tiebreaker so Python never compares the payload objects.
Skip empty lists when seeding the heap, and guard ei + 1 < len(lists[li]) before pushing the next element, or you index out of bounds.
Advance the pointer of the list you just popped from — not a global pointer. Carrying listIndex in the tuple is what makes "the same list" unambiguous.
Pairwise divide-and-conquer is the heap-free alternative: merge lists two at a time over log k rounds — also O(N log k), and easy when no heap is available.
For kth smallest in a sorted matrix, you don't materialize the full merge — just pop k times and return the kth popped value.

Merge k sorted streams — the heap pattern from this lesson:

→ Going deeper: K-way merge is the heap application that shows up in search and logs. See Heaps / priority queues.

→ Going deeper: Merging sorted lists is greedy; Kruskal MST sorts edges the same way. See Minimum spanning tree.