K-way Merge — How the Pattern Works
K-way Merge combines k individually sorted sequences—whether explicit arrays and linked lists or implicit virtual rows generated on demand—into a single globally sorted stream without concatenating and re-sorting all N elements. By tracking one frontier cursor per sequence inside a min-heap of size at most k, the algorithm maintains the invariant that the smallest unprocessed element across the entire input must be one of those k active heads. Popping the minimum head and pushing only its immediate successor from the originating sequence lowers full-merge time from O(N log N) to O(N log k) (and O(m + n) with O(1) space when k = 2), while answering k-th smallest queries in O(k log m) time.
- Merging k sorted arrays, streams, or singly linked lists into a single sorted output (from the k = 2 in-place array base case to arbitrary k).
- Finding the k-th smallest value across m sorted lists or inside a row-and-column-sorted 2D matrix without sorting all N elements.
- Extracting the k smallest pairs, sums, or fractions f(A[i], B[j]) across two sorted arrays A and B, where fixing index i produces a monotonically sorted virtual row over j.
- Generating an ascending sequence of numbers closed under multiplication by a fixed set of k prime factors (Ugly / Super Ugly number streams).
- Pushing non-comparable objects directly in heap tuples: in Merge K Sorted Lists, pushing (node.val, node) raises a TypeError in Python whenever two nodes tie on node.val; always insert a unique integer tie-breaker such as (node.val, list_idx, node).
- Enqueuing duplicate coordinates in 2D pair searches: pushing both (i + 1, j) and (i, j + 1) on each pop visits (1, 1) twice unless guarded by a visited set; instead, seed (i, 0) for 0 <= i < min(k, len(A)) and advance strictly along (i, j + 1).
- Ordering rational numbers with floating-point division: float precision loss can misorder close fractions a / b and c / d; implement custom __lt__ comparison via exact integer cross-multiplication a * d < c * b.
- Double-counting cross-stream duplicates in generative merges: in Super Ugly Number, products like 2 * 7 and 7 * 2 both yield 14; skip appending when val == result[-1], yet still advance that factor's cursor j + 1.
from heapq import heapify, heappush, heappop
def kth_across_lists(lists, k):
heap = [(s[0], i, 0) for i, s in enumerate(lists) if s]
heapify(heap)
while heap:
val, i, j = heappop(heap)
k -= 1
if k == 0:
return val
if j + 1 < len(lists[i]):
heappush(heap, (lists[i][j + 1], i, j + 1))from heapq import heapify, heappush, heappop
def k_smallest_virtual_rows(A, B, k):
heap = [(A[i] + B[0], i, 0) for i in range(min(k, len(A)))]
heapify(heap)
res = []
while heap and len(res) < k:
_, i, j = heappop(heap)
res.append([A[i], B[j]])
if j + 1 < len(B):
heappush(heap, (A[i] + B[j + 1], i, j + 1))
return resdef merge_from_back(nums1, m, nums2, n):
p1, p2, write = m - 1, n - 1, m + n - 1
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1