Definition
- K-way merge – combining K sorted lists into one by always selecting the global minimum from K candidates.
- Min-heap – a
PriorityQueueof size K holding one node per active list; the smallest node is always at the top. - Poll-and-push – poll the smallest node, attach it to the result, push the node's successor; the heap size stays at most K.
- Complexity – O(N log K) time because each of N nodes enters and leaves the heap once; O(K) space for the heap.
- Comparator – order nodes by
BigDecimal.compareTofor correct money value ordering.
The National Bank of India receives K sorted cheque piles from K branches, each pile sorted by amount from smallest on top. A clerk places the top cheque from every pile into a small tray of size K that instantly tells which cheque is smallest. The clerk takes that smallest cheque, puts it on the final pile, and replaces it in the tray with the next cheque from the same branch. The tray never holds more than K cheques.
Understanding the Concepts
What is the merge K sorted lists problem?
You are given an array of K linked list heads, each list sorted in ascending order. The goal is to merge all K lists into a single sorted linked list efficiently. This is the foundational problem of the K-way merge pattern, commonly used in external sorting and multi-stream aggregation.
package com.bank.model;
import java.math.BigDecimal;
public class SettlementNode {
public String branchId;
public BigDecimal amount;
public SettlementNode next;
public SettlementNode(String branchId, BigDecimal amount) {
this.branchId = branchId;
this.amount = amount;
}
}
How does the min-heap approach work?
Seed a PriorityQueue with the head of every non-empty list. Loop while the heap is not empty: poll the smallest node, attach it to the result using a dummy head pattern, and push the polled node's successor if it exists.
package com.bank.service;
import com.bank.model.SettlementNode;
import java.math.BigDecimal;
import java.util.PriorityQueue;
public class KListMerger {
public static SettlementNode mergeKLists(SettlementNode[] lists) {
PriorityQueue<SettlementNode> heap = new PriorityQueue<>(
(a, b) -> a.amount.compareTo(b.amount)
);
for (SettlementNode head : lists) {
if (head != null) {
heap.offer(head);
}
}
SettlementNode dummy = new SettlementNode("DUMMY", BigDecimal.ZERO);
SettlementNode tail = dummy;
while (!heap.isEmpty()) {
SettlementNode smallest = heap.poll();
tail.next = smallest;
tail = tail.next;
if (smallest.next != null) {
heap.offer(smallest.next);
}
}
return dummy.next;
}
public static void main(String[] args) {
SettlementNode l1 = new SettlementNode("HDFC", new BigDecimal("1000"));
l1.next = new SettlementNode("HDFC", new BigDecimal("5000"));
SettlementNode l2 = new SettlementNode("ICICI", new BigDecimal("2000"));
l2.next = new SettlementNode("ICICI", new BigDecimal("8000"));
SettlementNode l3 = new SettlementNode("SBI", new BigDecimal("3000"));
l3.next = new SettlementNode("SBI", new BigDecimal("7000"));
SettlementNode merged = mergeKLists(new SettlementNode[]{l1, l2, l3});
SettlementNode cur = merged;
while (cur != null) {
System.out.println(cur.branchId + " : " + cur.amount);
cur = cur.next;
}
}
}
HDFC : 1000
ICICI : 2000
SBI : 3000
HDFC : 5000
SBI : 7000
ICICI : 8000
Why is the heap size bounded by K?
The heap holds at most one node per active list. When you poll a node, you push at most one successor. So the size never exceeds K. This is what keeps each heap operation at O(log K) rather than O(log N).
Heap state during merge (K=3):
Start: [1000, 2000, 3000] size = 3
Poll 1000, push 5000: [2000, 3000, 5000] size = 3
Poll 2000, push 8000: [3000, 5000, 8000] size = 3
Poll 3000, push 7000: [5000, 7000, 8000] size = 3
...
When a list is exhausted, heap shrinks below K
How is this different from naive pairwise merge?
Merging lists one pair at a time in sequence re-walks already-merged elements and degrades to O(N * K). The heap approach touches each node exactly once for insertion and extraction.
| Approach | Time | Space |
|---|---|---|
| Heap-based K-way merge | O(N log K) | O(K) |
| Sequential pairwise merge | O(N * K) | O(1) |
| Divide-and-conquer pairwise | O(N log K) | O(1) |
// NAIVE: merge one pair at a time (O(N*K) worst case)
public static SettlementNode mergeNaive(SettlementNode[] lists) {
SettlementNode result = null;
for (SettlementNode list : lists) {
result = mergeTwoLists(result, list); // re-walks result each time
}
return result;
}
What is the divide-and-conquer alternative?
Instead of a heap, you can pair adjacent lists and merge them, then pair the results and merge again, repeating for log K rounds. This also achieves O(N log K) time but uses O(1) extra space because it only relinks nodes.
public static SettlementNode mergeKDivideConquer(SettlementNode[] lists) {
if (lists == null || lists.length == 0) return null;
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i + interval < lists.length; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}
What are the edge cases?
Empty arrays, arrays with all null heads, and arrays with a single list are the key edge cases.
package com.bank.service;
import com.bank.model.SettlementNode;
import java.math.BigDecimal;
public class KMergeEdgeCases {
public static void main(String[] args) {
// Empty array
System.out.println("Empty: " + KListMerger.mergeKLists(new SettlementNode[]{}));
// All nulls
System.out.println("All null: " + KListMerger.mergeKLists(
new SettlementNode[]{null, null}));
// Single list
SettlementNode single = new SettlementNode("SBI", new BigDecimal("500"));
SettlementNode result = KListMerger.mergeKLists(new SettlementNode[]{single});
System.out.println("Single: " + result.branchId + " " + result.amount);
}
}
Empty: null
All null: null
Single: SBI 500
Why use compareTo for BigDecimal in the comparator?
Never compare money with equals or subtraction. BigDecimal.equals checks scale, so 5000 and 5000.00 are not equal. compareTo checks numeric value only, which is what you want for ordering.
import java.math.BigDecimal;
// WRONG: subtraction-based comparator can overflow with extreme values
// and does not handle BigDecimal correctly
(a, b) -> a.amount.subtract(b.amount).intValue() // never do this
// CORRECT: compareTo handles all BigDecimal edge cases
(a, b) -> a.amount.compareTo(b.amount)
What should a senior engineer know?
The K-way merge pattern appears in external sorting (merging K sorted files), database query execution (merging sorted index scans), and stream processing. The heap-based version streams naturally as data arrives, which fits a feed-based banking system where branch settlement data arrives incrementally.
In production at National Bank of India, we use this to aggregate settlement feeds from multiple regional branches, each sending instructions already sorted by amount. The central engine maintains a size-K min-heap and drains it into one globally sorted stream for the ledger writer.
// In a streaming context, you can lazily pull from each list
// and the heap ensures globally sorted output at all times
while (!heap.isEmpty()) {
SettlementNode next = heap.poll();
ledgerWriter.write(next.branchId, next.amount);
if (next.next != null) heap.offer(next.next);
}
Visual Overview
K-Way Merge with Min-Heap (K=3) List 1 (HDFC): [1000] ──> [5000] List 2 (ICICI): [2000] ──> [8000] List 3 (SBI): [3000] ──> [7000] Min-Heap (size <= K): ┌─────────┐ │ 1000 │ ← poll this, push 5000 │ 2000 │ │ 3000 │ └─────────┘ Result chain grows one node at a time: [1000] ──> [2000] ──> [3000] ──> [5000] ──> [7000] ──> [8000]
Divide-and-Conquer Alternative (K=4)
Round 1: merge pairs
List1 + List2 → Merged12
List3 + List4 → Merged34
Round 2: merge results
Merged12 + Merged34 → Final
Total: log2(K) = 2 rounds, each touching N nodes → O(N log K)
Key Takeaway
Merging K sorted linked lists efficiently requires a min-heap that holds exactly one candidate node from each list. You seed the heap with every non-empty list's head, then repeatedly poll the global minimum, attach it to the result, and push the polled node's successor to keep that list represented. The heap never exceeds K entries, so each operation is O(log K), and the total merge costs O(N log K) time and O(K) space.
The naive approach of merging lists one pair at a time in sequence re-walks already-merged elements and degrades to O(N * K). The heap avoids this by touching each node exactly once. A divide-and-conquer variant that pairs and merges lists in log K rounds achieves the same time complexity with O(1) extra space, and is preferred when memory is very tight.
The comparator must use BigDecimal.compareTo for money values, because equals also checks decimal scale and would give wrong ordering for values like 5000 versus 5000.00. This is a common pitfall in financial software that the heap comparator must get right.
In our banking system at National Bank of India, we use the K-way merge to aggregate nightly settlement feeds from multiple regional branches. Each branch sends its instructions already sorted by amount, and the central engine maintains a size-K min-heap to produce one globally sorted stream for the ledger writer. The heap approach streams naturally as branch data arrives incrementally.
Remember one sentence: seed K heads into a min-heap, poll the smallest, push its successor, and the heap guarantees globally sorted output in O(N log K).
---