K-Way Merge

What you'll learn

• The Golden Rule

  When given K sorted arrays/lists and you need to merge them or find an element across all of them, use a min-heap of size K. The heap always holds one element from each of the K lists. Its root is the global minimum across all K fronts.…

• Why a Heap of Size K?

  Without a heap, finding the minimum across K lists requires scanning all K fronts — O(K) per element, O(NK) total. With a min-heap of size K: - Extracting the minimum: O(log K) - Inserting the next element: O(log K) - Total for N element…

• ASCII Trace: Merging 3 Sorted Lists

• Pattern 1: Merge K Sorted Lists

  The classic problem. Merge K sorted linked lists into one sorted list. Why include listidx in the tuple? Two reasons: 1. It tells us which list to pull the next element from 2. It breaks ties when two elements have the same value (avoidi…

• Pattern 2: Kth Smallest in a Sorted Matrix

  A matrix where each row and each column is sorted. Find the Kth smallest element. Key insight: Treat each row as one of K sorted lists. Use K-way merge but stop after extracting K elements.

• Pattern 3: Smallest Range Covering Elements from K Lists

  Find the smallest range [a, b] such that at least one element from each of the K lists falls within [a, b]. Strategy: - Maintain a min-heap with one element from each list (the current window) - Track the current maximum across all K rep…

• Pattern 4: Find K Pairs with Smallest Sums

  Given two sorted arrays, find K pairs (one element from each) with the smallest sums. Insight: Think of this as a virtual matrix where cell (i,j) = nums1[i] + nums2[j]. Each row is sorted. Apply K-way merge on this virtual matrix.

• Complexity Summary

  | Problem | Time | Space | |---------|------|-------| | Merge K sorted lists | O(N log K) | O(K) | | Kth smallest in matrix | O(K log K) | O(K) | | Smallest range | O(N log K) | O(K) | | K smallest pairs | O(K log K) | O(K) | Where N = t…

• External Merge Sort: Sorting Data Larger Than Memory

  When you need to sort a file that does not fit in RAM (e.g., 100 GB file on a machine with 8 GB RAM), external merge sort is the standard approach. It is a direct application of K-way merge.

• Algorithm

• Complexity Analysis

• Practical Considerations

  | Factor | Decision | |--------|----------| | Chunk size | Maximize to fit in available RAM (minus runtime overhead) | | Buffer size | Use large I/O buffers (4-8 MB) to minimize disk seeks | | Number of chunks | If too many (thousands),…

• When K is Too Large

  If N/C produces thousands of chunks, maintain too many open file handles and heap operations become expensive. Solution: multi-pass merging. Each pass reduces the number of chunks by a factor of T (merge width). Total passes needed: ceil…

• Example Calculation

  ---

• Key Takeaways

  1. Min-heap of size K — one representative per sorted list 2. Pop-and-advance: extract minimum, push next from same source 3. O(N log K) vs naive O(NK) — the heap saves a factor of K/log K 4. Track indices: store (value, listindex, eleme…