K-Way Merge Pattern: Heaps, Streams & External Sorting

When merging two sorted arrays into one, the standard two-pointer technique runs in linear time O(N). But when you need to merge K sorted lists, streams, or disk partitions containing a total of N elements, naive approaches quickly break down:

• Repeated Pairwise Merging: Merging list 1 with list 2, then merging that result with list 3 takes O(K × N) time.
• Concat and Full Sort: Concatenating all elements and running QuickSort takes O(N log N) and throws away existing sort ordering.
• K-Way Merge via Min-Heap: By maintaining a min-heap containing only 1 candidate from each of the K lists, finding the global minimum takes O(log K), achieving an optimal O(N log K) time with O(K) auxiliary space.

The Min-Heap Execution Pipeline

sequenceDiagram
    autonumber
    participant S as Input Streams (K = 3)
    participant H as Min-Heap (Size K)
    participant O as Merged Output Stream

    Note over S, H: ── PHASE 1: INITIALIZATION ──
    S->>H: Push initial head from each stream [1, 2, 3]
    activate H
    Note over H: Min-heap rebalances in O(log K)
Minimum item (1) is at root
    deactivate H

    Note over H, O: ── PHASE 2: EXTRACT & REFILL ──
    H->>O: Poll minimum element (1)
    activate O
    Note over O: Merged output: [1]
    deactivate O

    S->>H: Push next element (7) from Stream 1
    activate H
    Note over H: Min-heap rebalances in O(log K)
New minimum item (2) is at root
    deactivate H

    H->>O: Poll minimum element (2)
    activate O
    Note over O: Merged output: [1, 2]
    deactivate O

    S->>H: Push next element (6) from Stream 0
    activate H
    Note over H: Repeat cycle until all K streams are empty
    deactivate H

1. Seed the Heap: Insert the first element of each of the K lists into a min-heap alongside its source stream index and element index.
2. Extract Minimum: Pop the root node (smallest across all lists) and append its value to the output stream.
3. Advance the Source: Read the next item from the specific list that produced the extracted minimum. Push it into the heap.
4. Termination: Repeat until all K streams are fully exhausted.

Pattern 1: Merging K Sorted Linked Lists

A classic technical interview and systems problem: combine K sorted singly linked lists into a single consolidated sorted list.

Java Implementation

import java.util.PriorityQueue;

public class KWayMergeLists {
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Min-heap ordered by node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );

        // Seed heap with the head of each non-empty list
        for (ListNode root : lists) {
            if (root != null) {
                minHeap.offer(root);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;

            // Advance the pointer within the extracted node's list
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }

        return dummyHead.next;
    }
}

Python Implementation

import heapq
from typing import List, Optional

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

def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    
    # Store tuples: (val, unique_id, node) to avoid unorderable comparison errors
    for idx, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, idx, node))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        val, idx, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next

        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

Pattern 2: Finding Kth Smallest Element in an N × N Matrix

Given an N × N matrix where every row and column is sorted in ascending order, how do you find the k-th smallest number efficiently?

Instead of treating it as a raw 2D array, treat each row as one of N sorted streams. Insert the first element of each row into a min-heap and pop k - 1 times. The k-th popped element is the answer.

TypeScript Implementation

interface HeapNode {
  val: number;
  row: number;
  col: number;
}

export function kthSmallestInMatrix(matrix: number[][], k: number): number {
  const n = matrix.length;
  // Simulating a Min-Heap with an ordered buffer or PriorityQueue
  const heap: HeapNode[] = [];

  const push = (node: HeapNode) => {
    heap.push(node);
    heap.sort((a, b) => a.val - b.val);
  };

  // Seed with first element of up to min(n, k) rows
  const maxRows = Math.min(n, k);
  for (let r = 0; r < maxRows; r++) {
    push({ val: matrix[r][0], row: r, col: 0 });
  }

  let count = 0;
  let result = 0;

  while (heap.length > 0) {
    const minNode = heap.shift()!;
    count++;
    result = minNode.val;

    if (count === k) {
      return result;
    }

    if (minNode.col + 1 < n) {
      push({
        val: matrix[minNode.row][minNode.col + 1],
        row: minNode.row,
        col: minNode.col + 1
      });
    }
  }

  return result;
}

Real-World Systems Architecture: External Merge Sort

K-Way merge is the foundation of External Merge Sort used in distributed databases and query engines (e.g., PostgreSQL, Apache Spark, SQLite) when dataset sizes exceed available RAM:

1. Chunk & Sort: The engine reads chunks of data that fit into RAM (say 1GB each), sorts them in-memory, and writes sorted runs to temporary disk storage.
2. Multi-Way Merging: If you have 100 sorted runs on disk, allocating a small read-buffer (e.g., 8KB) for each run allows a single min-heap of size K = 100 in RAM to stream the final sorted file straight to disk or output socket in a single streaming pass.

Complexity Analysis & Comparison