Definition
- Min-heap of k fronts – holds one element per list, ordered by value.
- Poll and push – extract the smallest, append to output, push the next element from that list.
- O(N log k) – each element is pushed and polled once at O(log k).
- Source tracking – wrap each value with its list index and position to know where to advance.
- External merge – this is exactly how multi-way merge sort combines sorted runs from disk.
Imagine the National Bank of India has k branch ledgers, each already sorted by transaction time, and wants one combined ledger in time order. A clerk looks at the earliest unprocessed entry from each branch, picks the single earliest among them, writes it into the combined ledger, then looks at the next entry from just that branch. She keeps a tiny sorted tray with one entry per branch.
Understanding the Concepts
What is the problem?
Given k sorted lists (arrays), merge them into one sorted list efficiently using a priority queue. The key insight is that each list is already sorted, so you only ever need to compare the current fronts of the k lists.
package com.bank.sort;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MergeKSortedArrays {
public static List<Integer> merge(int[][] lists) {
// Entry: [value, listIndex, elementIndex]
PriorityQueue<int[]> heap = new PriorityQueue<>(
Comparator.comparingInt(e -> e[0]));
for (int i = 0; i < lists.length; i++) {
if (lists[i].length > 0) {
heap.offer(new int[]{lists[i][0], i, 0});
}
}
List<Integer> result = new ArrayList<>();
while (!heap.isEmpty()) {
int[] top = heap.poll();
result.add(top[0]);
int li = top[1], ei = top[2];
if (ei + 1 < lists[li].length) {
heap.offer(new int[]{lists[li][ei + 1], li, ei + 1});
}
}
return result;
}
public static void main(String[] args) {
int[][] lists = {
{10000, 30000, 50000},
{20000, 40000},
{15000, 25000, 60000}
};
System.out.println("Merged: " + merge(lists));
}
}
Merged: [10000, 15000, 20000, 25000, 30000, 40000, 50000, 60000]
How does the source tracking work?
Each entry in the heap stores three values: the element value, the list index it came from, and the position within that list. When you poll an entry, you know which list to advance by reading its list index and incrementing the position.
package com.bank.sort;
import java.util.PriorityQueue;
import java.util.Comparator;
public class SourceTracking {
public static void main(String[] args) {
int[][] lists = {{10, 30}, {20, 40}, {15, 25}};
PriorityQueue<int[]> heap = new PriorityQueue<>(
Comparator.comparingInt(e -> e[0]));
for (int i = 0; i < lists.length; i++) {
heap.offer(new int[]{lists[i][0], i, 0});
}
while (!heap.isEmpty()) {
int[] top = heap.poll();
System.out.println("Value=" + top[0]
+ " from list " + top[1] + " pos " + top[2]);
if (top[2] + 1 < lists[top[1]].length) {
heap.offer(new int[]{lists[top[1]][top[2]+1], top[1], top[2]+1});
}
}
}
}
Value=10 from list 0 pos 0
Value=15 from list 2 pos 0
Value=20 from list 1 pos 0
Value=25 from list 2 pos 1
Value=30 from list 0 pos 1
Value=40 from list 1 pos 1
How does this compare to the naive approach?
| Approach | Time | Space | Exploits sorted? |
|---|---|---|---|
| Concatenate + sort | O(N log N) | O(N) | No |
| Min-heap k-way | O(N log k) | O(k) | Yes |
| Pairwise merge | O(N log k) | O(1) | Yes |
How is this used with BigDecimal for money?
For financial data, each list contains BigDecimal amounts. The heap's comparator uses compareTo instead of integer comparison.
package com.bank.sort;
import java.math.BigDecimal;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
public class MergeBigDecimalLists {
record Entry(BigDecimal value, int listIdx, int elemIdx) {}
public static List<BigDecimal> merge(BigDecimal[][] lists) {
PriorityQueue<Entry> heap = new PriorityQueue<>(
Comparator.comparing(Entry::value));
for (int i = 0; i < lists.length; i++) {
if (lists[i].length > 0) {
heap.offer(new Entry(lists[i][0], i, 0));
}
}
List<BigDecimal> result = new ArrayList<>();
while (!heap.isEmpty()) {
Entry top = heap.poll();
result.add(top.value());
int next = top.elemIdx() + 1;
if (next < lists[top.listIdx()].length) {
heap.offer(new Entry(lists[top.listIdx()][next], top.listIdx(), next));
}
}
return result;
}
public static void main(String[] args) {
BigDecimal[][] lists = {
{new BigDecimal("10000.50"), new BigDecimal("30000.75")},
{new BigDecimal("20000.25"), new BigDecimal("40000.00")}
};
System.out.println("Merged: " + merge(lists));
}
}
Merged: [10000.50, 20000.25, 30000.75, 40000.00]
What is the time and space complexity?
| Metric | Value |
|---|---|
| Time | O(N log k) |
| Space | O(k) for the heap |
| N | Total elements across all lists |
| k | Number of lists |
How does this relate to external merge sort?
External merge sort splits a large file into sorted runs that fit in memory, then merges them using exactly this k-way merge. The heap holds one element per run, and the merge proceeds by polling the smallest and advancing that run. Banks use this to merge enormous sorted transaction files.
package com.bank.sort;
public class ExternalMerge {
public static void main(String[] args) {
System.out.println("External merge sort:");
System.out.println("1. Split large file into sorted chunks (runs)");
System.out.println("2. Open k runs simultaneously");
System.out.println("3. Use min-heap with one element per run");
System.out.println("4. Poll smallest, write to output, read next from that run");
System.out.println("5. Result: one fully sorted file");
}
}
External merge sort:
1. Split large file into sorted chunks (runs)
2. Open k runs simultaneously
3. Use min-heap with one element per run
4. Poll smallest, write to output, read next from that run
5. Result: one fully sorted file
What is the pairwise merge alternative?
Instead of a heap, pair up the k lists and merge them two at a time in log k rounds. This also achieves O(N log k) but avoids the heap overhead and uses O(1) extra space for the merge itself.
package com.bank.sort;
public class PairwiseAlternative {
public static void main(String[] args) {
System.out.println("Pairwise merge:");
System.out.println("Round 1: merge list 0+1, 2+3, 4+5 -> k/2 lists");
System.out.println("Round 2: merge pairs again -> k/4 lists");
System.out.println("...after log k rounds: 1 sorted list");
System.out.println("Same O(N log k) time, no heap needed.");
}
}
Pairwise merge:
Round 1: merge list 0+1, 2+3, 4+5 -> k/2 lists
Round 2: merge pairs again -> k/4 lists
...after log k rounds: 1 sorted list
Same O(N log k) time, no heap needed.
What are common mistakes?
The most common mistakes are: forgetting to check for empty lists when seeding the heap, not tracking which list an element came from (causing wrong advancement), and using a max-heap instead of a min-heap.
Visual Overview
k-Way Merge with Min-Heap:
List 0: [10, 30, 50]
List 1: [20, 40]
List 2: [15, 25]
Heap entries: [value, listIdx, elemIdx]
Seed: [{10,0,0}, {20,1,0}, {15,2,0}]
Poll 10: output 10, push {30,0,1} -> heap: [{15,2,0}, {20,1,0}, {30,0,1}]
Poll 15: output 15, push {25,2,1} -> heap: [{20,1,0}, {25,2,1}, {30,0,1}]
Poll 20: output 20, push {40,1,1} -> heap: [{25,2,1}, {30,0,1}, {40,1,1}]
Poll 25: output 25, list 2 done -> heap: [{30,0,1}, {40,1,1}]
Poll 30: output 30, push {50,0,2} -> heap: [{40,1,1}, {50,0,2}]
Poll 40: output 40, list 1 done -> heap: [{50,0,2}]
Poll 50: output 50, list 0 done -> heap: []
Output: [10, 15, 20, 25, 30, 40, 50]
Key Takeaway
Merging k sorted lists means producing one sorted output by repeatedly taking the smallest unconsumed element across all lists. A min-heap holding one candidate from each list makes finding the smallest a O(log k) operation. You poll the smallest, append it, and push the next element from whichever list that one came from.
Because the heap only holds one representative per list, its size stays at most k, so every poll and push is O(log k). Over all N elements the total is O(N log k) with O(k) space. To track which list to advance, each heap entry stores its value, list index, and element position.
This is exactly how external merge sort combines sorted runs from disk. At the National Bank of India, end-of-day transaction files from several branches, each already sorted, are merged into one globally sorted file for settlement using this k-way merge.
The pairwise divide-and-conquer merge is an equally efficient alternative at O(N log k) without a heap. The heap version is simpler and naturally streaming.
Remember one sentence: keep one element per list in a min-heap, poll the smallest and push its successor, and the output comes out sorted in O(N log k) time.
---