Skip to content
← All Patterns
← Two HeapsFast & Slow Pointers →
Sorting & SearchingIntermediate

K-way Merge

Merge K sorted arrays or lists using a min-heap to always pick the globally smallest element across all lists.

Initial Lists

Merge 3 sorted lists: [1,4,7], [2,5,8], [3,6,9]

Min-Heap: Initialize with first element from each list
List 0: [1,4,7] List 1: [2,5,8] List 2: [3,6,9]
Step 1/10
Speed:

When to Use

  • Merge K sorted arrays or linked lists
  • Find the smallest range covering K lists
  • External sort (merge sorted chunks)
  • Kth smallest in a sorted matrix

Key Indicators

  • K sorted inputs to merge
  • Smallest element across multiple sorted sources
  • Sorted matrix queries
  • Multiple sorted streams

Complexity

Time

O(N log K)

Space

O(K)

Common Problems

Merge K Sorted ListsSmallest Range Covering Elements from K ListsKth Smallest Element in a Sorted MatrixMerge Two Sorted Lists

Code

heap = []
for i in range(K):
    heappush(heap, (lists[i][0], i, 0))

result = []
while heap:
    val, list_idx, elem_idx = heappop(heap)
    result.append(val)
    if elem_idx + 1 < len(lists[list_idx]):
        next_val = lists[list_idx][elem_idx + 1]
        heappush(heap, (next_val, list_idx, elem_idx + 1))

Want all 29 patterns with detailed visual walkthroughs?

The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.

Book Coming Soon ($4.99)