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; each poll and push is O(log K). - Invariant – the heap holds at most one node per active list; a successor is pushed only after its predecessor is polled.
- Complexity – O(N log K) time, O(K) space.
- Dummy head – a sentinel node that simplifies the append logic.
The National Bank of India has K branch ledgers, each already sorted by transaction time. Rajesh needs one combined statement in time order. Instead of dumping everything and re-sorting, a clerk keeps the earliest unread line from each branch on a small desk of size K, always picks the globally earliest, writes it down, and replaces it with the next line from that same branch.
Understanding the Concepts
What is the K-way merge pattern?
Given K sorted linked lists, merge them into one sorted list. The K-way merge pattern exploits the existing order: instead of concatenating all N nodes and re-sorting (O(N log N)), you only ever compare K current heads at a time using a min-heap.
package com.bank.model;
import java.math.BigDecimal;
public class TxnNode {
public String branchId;
public BigDecimal amount;
public long timestamp;
public TxnNode next;
public TxnNode(String branchId, BigDecimal amount, long timestamp) {
this.branchId = branchId;
this.amount = amount;
this.timestamp = timestamp;
}
}
How does the heap-based approach work?
Seed a PriorityQueue with each list's head. Loop: poll the smallest, attach to result, push its successor. The heap never exceeds K entries.
package com.bank.service;
import com.bank.model.TxnNode;
import java.math.BigDecimal;
import java.util.PriorityQueue;
public class KWayMerger {
public static TxnNode mergeKLists(TxnNode[] lists) {
PriorityQueue<TxnNode> heap = new PriorityQueue<>(
(a, b) -> Long.compare(a.timestamp, b.timestamp)
);
for (TxnNode head : lists) {
if (head != null) heap.offer(head);
}
TxnNode dummy = new TxnNode("DUMMY", BigDecimal.ZERO, 0);
TxnNode tail = dummy;
while (!heap.isEmpty()) {
TxnNode 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) {
TxnNode l1 = new TxnNode("HDFC", new BigDecimal("1000"), 100);
l1.next = new TxnNode("HDFC", new BigDecimal("3000"), 300);
TxnNode l2 = new TxnNode("ICICI", new BigDecimal("2000"), 200);
l2.next = new TxnNode("ICICI", new BigDecimal("4000"), 400);
TxnNode l3 = new TxnNode("SBI", new BigDecimal("2500"), 250);
TxnNode merged = mergeKLists(new TxnNode[]{l1, l2, l3});
TxnNode cur = merged;
while (cur != null) {
System.out.println(cur.branchId + " t=" + cur.timestamp + " amt=" + cur.amount);
cur = cur.next;
}
}
}
HDFC t=100 amt=1000
ICICI t=200 amt=2000
SBI t=250 amt=2500
HDFC t=300 amt=3000
ICICI t=400 amt=4000
Why is the heap bounded at K?
The heap holds at most one node per active list. When you poll a node, you push at most one successor from the same list. So the size never exceeds K, keeping each operation at O(log K).
Heap state (K=3):
Start: [t=100, t=200, t=250] size=3
Poll t=100: [t=200, t=250, t=300] size=3 (pushed t=300)
Poll t=200: [t=250, t=300, t=400] size=3 (pushed t=400)
Poll t=250: [t=300, t=400] size=2 (SBI exhausted)
How does the divide-and-conquer alternative work?
Pair adjacent lists and merge them in log K rounds. This achieves O(N log K) time with O(1) extra space because it only relinks existing nodes.
public static TxnNode mergeKDivideConquer(TxnNode[] 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 is the complexity comparison?
| Approach | Time | Space |
|---|---|---|
| Min-heap K-way merge | O(N log K) | O(K) |
| Divide-and-conquer pairwise | O(N log K) | O(1) |
| Sequential pairwise | O(N * K) | O(1) |
| Concatenate and sort | O(N log N) | O(N) |
What are the edge cases?
Empty array, array of all nulls, single list, and lists of vastly different lengths.
System.out.println(KWayMerger.mergeKLists(new TxnNode[]{})); // null
System.out.println(KWayMerger.mergeKLists(new TxnNode[]{null})); // null
Why use the dummy head pattern?
The dummy head eliminates special-casing the first node. Every attachment uses the same tail.next = node pattern, and the result starts at dummy.next.
TxnNode dummy = new TxnNode("DUMMY", BigDecimal.ZERO, 0);
TxnNode tail = dummy;
// ... loop appends to tail.next uniformly ...
return dummy.next; // skip the dummy
What should a senior engineer know?
The K-way merge pattern appears in external sorting (merging K sorted files from disk), database query execution (merging sorted index scans), and stream processing. The heap approach streams naturally, which fits feed-based banking systems.
In production at National Bank of India, the central ledger merges K branch transaction feeds, each pre-sorted by timestamp, into one globally ordered stream.
// Production streaming merge
while (!heap.isEmpty()) {
TxnNode next = heap.poll();
ledgerWriter.write(next);
if (next.next != null) heap.offer(next.next);
}
Visual Overview
K-Way Merge with Min-Heap (K=3) HDFC: [t=100] ──> [t=300] ICICI: [t=200] ──> [t=400] SBI: [t=250] Heap (sorted by timestamp): ┌─────────┐ │ t=100 │ ← poll, push t=300 │ t=200 │ │ t=250 │ └─────────┘ Result: [100] → [200] → [250] → [300] → [400]
Divide-and-Conquer Rounds (K=4) Round 1: merge(L1, L2) → M12 merge(L3, L4) → M34 Round 2: merge(M12, M34) → Final log2(K) = 2 rounds, each touching N nodes Total: O(N log K)
Key Takeaway
The K-way merge pattern combines K sorted linked lists into one by maintaining a min-heap that holds one candidate from each active 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. The heap never exceeds K entries, so the total cost is O(N log K) time and O(K) space.
The approach exploits the existing sort order of each list, unlike concatenating everything and re-sorting which would be O(N log N). A divide-and-conquer variant pairs lists and merges in log K rounds, achieving the same time complexity with O(1) extra space.
The dummy head pattern keeps the append logic uniform: every node is attached with the same tail.next = node code, and the result starts at dummy.next. The heap comparator should use the appropriate field for ordering: timestamps for chronological merging, BigDecimal.compareTo for amount-based ordering.
In our banking system at National Bank of India, the central ledger merges K branch transaction feeds, each pre-sorted by timestamp, into one globally ordered stream. The heap approach streams naturally as branch data arrives incrementally, and the size-K heap invariant keeps memory bounded regardless of total transaction volume.
Remember one sentence: seed K heads into a min-heap, poll smallest, push successor, and the heap produces a globally sorted stream in O(N log K).
---