TLDR: K-Way Merge uses a min-heap with exactly one entry per sorted input list. Each entry stores the current element's value plus the coordinates to find the next element in that list. Pop the minimum (global smallest), append it to output, push the next element from the same list. Repeat until the heap is empty. Time: O(N log K) for N total elements across K lists.

---

📖 Merging K Server Log Files Without Loading All of Them in Memory

You have K sorted log files — one from each server in your cluster. Each file records events in ascending timestamp order. You need to merge them into one unified timeline for analysis. The brute-force approach (concatenate all files, then sort) loads every log line into memory and sorts O(N log N). For 50 servers with 1 million lines each, that is 50 million records in RAM and 50M × 25 ≈ 1.25 billion comparisons.

K-Way Merge solves this in O(N log K): it reads exactly one line at a time per file, always selecting the globally earliest timestamp using a min-heap. Memory use is O(K) — just K pointers into K files, not the full content. For K=50, that is 50 heap entries regardless of how many lines each file has.

This is not just a log-file trick. Whenever you have K already-sorted sequences that need to be combined into one sorted sequence, K-Way Merge is the optimal algorithm. It is the core of database merge-join operations, external sort algorithms, and distributed reduce phases.

---

🔍 The Min-Heap Pointer: Always Knowing Which List Has the Next Element

The central question in merging K sorted lists is: which list's current front element is the globally smallest? Answering this naively requires comparing all K front elements — O(K) per step, O(NK) total. A min-heap answers it in O(log K) per step.

The key mental model: the min-heap is a priority queue of "current positions" across all K lists, ordered by the value at each position. At any moment, the heap root tells you exactly which list holds the global minimum.

Here is the pattern with concrete language:

1. Seed the heap — push the first element from every non-empty list, tagged with (value, listIndex, elementIndex).
2. Pop the minimum — the heap root is the globally smallest element across all lists. Append it to the output.
3. Advance the pointer — push the next element from the same list (using the saved listIndex and elementIndex + 1). If that list is exhausted, push nothing.
4. Repeat until the heap is empty.

The element wrapper (value, listIndex, elementIndex) is what makes this work for arrays. For linked lists, you store the ListNode reference directly (its .val is the value; .next is the next pointer). Either way, the pattern is identical.

---

⚙️ The Element Wrapper: Tracking Value, List Index, and Element Index

For array-based problems, you need to encode three pieces of information in each heap entry: the current value (for comparison), the list it came from (to find the next element), and the position within that list (to advance the pointer).

In Java, an int[] of length 3 is the lightest-weight wrapper:

// heap entry: { value, listIndex, elementIndex }
int[] entry = new int[]{ lists[listIdx][elemIdx], listIdx, elemIdx };

The min-heap comparator orders entries by entry[0] (the value):

PriorityQueue<int[]> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0])
);

Worked example — merging three sorted arrays:

Lists: [1, 4, 7], [2, 5, 8], [3, 6, 9]

At every step, the heap has exactly K entries (or fewer, once a list is exhausted). The heap never needs to know about elements beyond the current front of each list.

---

🧠 Deep Dive: How the K-Way Merge Min-Heap Maintains Global Order

Internals: Min-Heap State and the Pointer Advancement Loop

Each heap entry is a triple (value, listIdx, elemIdx). The heap orders by value — a min-heap, so the root always holds the triple with the smallest value across all K lists.

After popping the root (v, l, e):

• Append v to the output.
• If lists[l] has an element at index e + 1, push (lists[l][e+1], l, e+1).
• Otherwise, that list is exhausted — nothing is pushed, and the heap shrinks by 1.

Invariant: at all times, the heap contains exactly the "current front element" of every non-exhausted list. This invariant is established by seeding and maintained by the push-after-pop rule. Because all input lists are sorted, the globally smallest remaining element is always at the heap root.

For linked lists, replace (value, listIdx, elemIdx) with ListNode references. The comparator compares node.val; advancing the pointer is node.next. The logic is identical — the wrapper is just a node reference instead of a coordinate triple.

Performance Analysis: O(N log K) for K Lists of Total N Elements

Comparison table:

The O(K) space advantage is decisive for external merge sort: when N is in the billions (database tables, HDFS files), you cannot load everything into RAM. K-Way Merge streams through the data, keeping only K active pointers in the heap.

---

📊 Watching Three Sorted Arrays Merge via Min-Heap State

The flowchart below shows the full K-Way Merge loop from seeding to output:

flowchart TD
    A([Start: K sorted lists]) --> B[Seed min-heap with first element\nof each non-empty list]
    B --> C{Heap is empty?}
    C -- No --> D[Pop root: smallest value + list coordinates]
    D --> E[Append value to merged output]
    E --> F{Next element exists in that list?}
    F -- Yes --> G[Push next element with updated index]
    F -- No --> H[List exhausted — do not push]
    G --> C
    H --> C
    C -- Yes --> I([Merged output is fully sorted])

For three arrays [1,4,7], [2,5,8], [3,6,9], the heap state after each pop cycles through all three lists in a round-robin fashion because the values are interleaved. In practice, lists with smaller values are drained faster and a list's pointer advances multiple steps before another list contributes — the heap rebalances automatically.

---

🌍 Real-World Applications: Log Aggregation, External Sort, and Database Merges

Distributed log aggregation — When a Kubernetes cluster routes logs from 100 pods through Fluentd or Fluent Bit to a central sink, each pod's log stream is already sorted by timestamp. K-Way Merge combines them in O(N log 100) — just 6.6× the cost of writing each event once. The alternative (sort all events after collecting) requires all events in memory and costs O(N log N).

External sort — When a dataset is too large for RAM (terabyte-scale database tables), the external sort algorithm works in two phases. Phase 1: split the file into K sorted runs that each fit in RAM. Phase 2: K-Way Merge combines those runs into one sorted file. This is exactly the algorithm used by PostgreSQL's disk sort, MySQL's filesort, and Apache Spark's sort-based shuffle.

Database merge join — SQL engines execute JOIN between two sorted relations using a two-way merge (K=2 case). When joining more than two pre-sorted partitions, the general K-Way Merge applies. The index merge access path in MySQL explicitly implements this for multi-index scans.

Case study — Apache Hadoop's merge sort phase:

In Hadoop's MapReduce shuffle, each mapper produces a sorted spill file. Multiple spill files are then merged by the reducer using K-Way Merge. The number of files merged at once (K) is controlled by mapreduce.task.io.sort.factor (default 10). See the OSS section for how to tune this.

---

⚖️ Trade-offs: K-Way Merge vs Two-Pointer vs Concatenate-and-Sort

The decision between approaches hinges on whether your lists are already sorted and how large K is:

Failure mode: unsorted input. K-Way Merge is only correct when each input list is sorted. If any list has unsorted elements, the heap's invariant breaks silently — the output looks reasonable but has wrong order. Always sort individual lists (or verify they are sorted) before running K-Way Merge.

Failure mode: K very large. If K approaches N (e.g., K = N/10), the heap itself costs O(K log K) = O(N log N) to maintain. At that point, concatenate-and-sort with O(N log N) is comparable in time and simpler to implement.

---

🧭 Decision Guide: When to Use K-Way Merge

---

🧪 Four Problems: Merge K Lists, Kth Smallest, Sorted Matrix, Smallest Range

Example 1 — Merge K Sorted Linked Lists

Given an array of K sorted linked lists, merge them into one sorted list.

import java.util.PriorityQueue;

public class MergeKSortedLists {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
                (a, b) -> a.val - b.val
        );

        // Seed: push the head of each non-null list
        for (ListNode node : lists) {
            if (node != null) minHeap.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;
            if (smallest.next != null) minHeap.offer(smallest.next); // advance pointer
        }
        return dummy.next;
    }
}

The dummy sentinel node eliminates a null-check for the head of the merged list. The comparator (a, b) -> a.val - b.val is safe here because ListNode.val is an int with bounded range in practice; for safety, use Integer.compare(a.val, b.val).

Example 2 — Kth Smallest Number in M Sorted Lists

Given M sorted arrays, find the Kth smallest number across all of them combined.

import java.util.PriorityQueue;
import java.util.Comparator;

public class KthSmallestMSortedLists {

    public int kthSmallest(int[][] lists, int k) {
        // heap entry: { value, listIndex, elementIndex }
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
                Comparator.comparingInt(a -> a[0])
        );

        for (int i = 0; i < lists.length; i++) {
            if (lists[i].length > 0) {
                minHeap.offer(new int[]{lists[i][0], i, 0});
            }
        }

        int count = 0;
        while (!minHeap.isEmpty()) {
            int[] entry = minHeap.poll();
            int val = entry[0], listIdx = entry[1], elemIdx = entry[2];
            if (++count == k) return val;
            if (elemIdx + 1 < lists[listIdx].length) {
                minHeap.offer(new int[]{lists[listIdx][elemIdx + 1], listIdx, elemIdx + 1});
            }
        }
        return -1; // k exceeds total element count
    }
}

This is the pure K-Way Merge loop: pop the minimum, count it, push the next from the same list. Stop as soon as count reaches K.

Example 3 — Kth Smallest Number in a Sorted Matrix

Given an N×N matrix where every row and column is sorted in ascending order, find the Kth smallest element.

import java.util.PriorityQueue;
import java.util.Comparator;

public class KthSmallestMatrix {

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // Treat each row as one sorted list
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
                Comparator.comparingInt(a -> a[0])
        );

        // Seed with the first element of each row (at most K rows matter)
        for (int i = 0; i < Math.min(n, k); i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }

        int count = 0;
        while (!minHeap.isEmpty()) {
            int[] entry = minHeap.poll();
            int val = entry[0], row = entry[1], col = entry[2];
            if (++count == k) return val;
            if (col + 1 < n) {
                minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
            }
        }
        return -1;
    }
}

The matrix is treated as N sorted rows. The heap merges those rows using the standard K-Way Merge loop. Seeding only min(n, k) rows is an optimization: the Kth smallest cannot come from row index ≥ k.

Example 4 — Smallest Range Covering Elements from K Lists

Given K sorted lists, find the smallest range [start, end] such that at least one element from each list falls in the range.

import java.util.*;

public class SmallestRange {

    public int[] smallestRange(List<List<Integer>> nums) {
        // heap entry: { value, listIndex, elementIndex }
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
                Comparator.comparingInt(a -> a[0])
        );
        int maxVal = Integer.MIN_VALUE;

        // Seed: one element per list; track current maximum
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            maxVal = Math.max(maxVal, val);
        }

        int[] result = {minHeap.peek()[0], maxVal};

        while (!minHeap.isEmpty()) {
            int[] entry = minHeap.poll();
            int val = entry[0], listIdx = entry[1], elemIdx = entry[2];

            // If any list is exhausted, we cannot cover all K lists further
            if (elemIdx + 1 >= nums.get(listIdx).size()) break;

            int nextVal = nums.get(listIdx).get(elemIdx + 1);
            minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
            maxVal = Math.max(maxVal, nextVal);

            // Current range: [minHeap.peek()[0], maxVal]
            if (maxVal - minHeap.peek()[0] < result[1] - result[0]) {
                result[0] = minHeap.peek()[0];
                result[1] = maxVal;
            }
        }
        return result;
    }
}

This problem adds a twist: instead of outputting all merged elements, you track the range [heap_root, current_max] that covers one element from every list (the min is the heap root; the max is tracked separately). When that range shrinks, update the answer. Stop as soon as any list is exhausted — at that point no range can cover all K lists.

---

🛠️ Apache Hadoop's Merge Sort Phase: K-Way Merge at Scale

Apache Hadoop's MapReduce shuffle is one of the largest-scale deployments of K-Way Merge in production. Here is how it works:

Phase 1 (map-side spills): Each mapper sorts its output into in-memory buffers. When a buffer fills, it is spilled to disk as a sorted file. A single mapper may produce dozens of spill files.

Phase 2 (merge): Before data is sent to reducers, the spill files are merged. Hadoop uses K-Way Merge with K controlled by:

<!-- mapred-site.xml -->
<property>
  <name>mapreduce.task.io.sort.factor</name>
  <value>10</value>  <!-- default: merge 10 sorted files at a time -->
</property>

Phase 3 (reduce-side merge): The reducer receives sorted partitions from multiple mappers. It applies K-Way Merge again across those partitions before passing values to the user's reduce() function.

The entire shuffle — billions of key-value pairs sorted across hundreds of nodes — reduces to repeated applications of K-Way Merge with the heap size bounded by io.sort.factor. Increasing this value reduces the number of merge passes needed for very large numbers of spills, at the cost of more open file handles and heap memory.

For a full deep-dive on Hadoop's shuffle and sort internals, see the Apache Hadoop MapReduce documentation on the shuffle and sort phase.

---

📚 Lessons Learned: Off-by-One Errors and Edge Cases in K-Way Merge

1. Forgetting to check bounds before pushing the next element. The most common runtime error is ArrayIndexOutOfBoundsException or NullPointerException when advancing the pointer. Always guard: if (elemIdx + 1 < lists[listIdx].length) before pushing. For linked lists: if (node.next != null).

2. Seeding null/empty lists. If any of the K input lists is null or empty, skip it during seeding. Pushing a null node or out-of-bounds index into the heap immediately corrupts the comparator.

3. Using a.val - b.val as a comparator for integer overflow. Safe only when values are bounded away from Integer.MIN_VALUE. For general cases, use Integer.compare(a.val, b.val) to eliminate overflow risk.

4. Confusing Kth smallest with Kth largest. K-Way Merge naturally produces the globally smallest first (because it uses a min-heap). To find the Kth largest, either count from the end (total elements minus K) or reverse the merge order with a max-heap — but max-heap K-Way Merge only works when all input lists are sorted in descending order.

5. Not handling K=1 as a special case in production code. When K=1, the heap contains a single entry at all times, and every poll/push is O(1) effectively (log 1 = 0). The algorithm is correct but the heap overhead is unnecessary — return the single list unchanged.

---

📌 Summary: K-Way Merge in Five Bullets

• Core idea: A min-heap acts as a global priority queue across K sorted lists. It always knows the next smallest element in O(log K), regardless of how many total elements remain.
• Time: O(N log K) — each of the N elements is pushed and popped exactly once, costing O(log K) per operation.
• Space: O(K) — the heap holds exactly one active entry per non-exhausted list, independent of N.
• The wrapper pattern: Always store (value, listIndex, elementIndex) or a ListNode reference in the heap so you can advance the pointer after each pop.
• Production use: K-Way Merge powers database external sort, Apache Hadoop/Spark shuffle merge, and distributed log aggregation — anywhere K sorted streams must be unified without loading all data into memory.

---

📝 Practice Quiz

1. You have K=100 sorted lists with a total of N=1,000,000 elements. What is the time complexity of K-Way Merge?

   • A) O(N log N)
   • B) O(N log K) = O(N × 6.6) ≈ O(N)
   • C) O(K × N) Correct Answer: B — Each of the N elements is pushed and popped from a heap of size at most K=100. Each heap operation is O(log 100) ≈ 6.6 steps. Total: O(N log K). When K ≪ N, this is effectively linear.

2. During K-Way Merge, after popping (value, listIdx, elemIdx) from the min-heap, what should you push next?

   • A) The minimum element from any list
   • B) The next element from lists[listIdx] at index elemIdx + 1, if it exists
   • C) Nothing — the heap re-balances automatically Correct Answer: B — You must advance the pointer in the same list that just produced the popped value. Pushing from any other list would break the invariant that each list has exactly one representative in the heap.

3. A sorted matrix problem asks for the Kth smallest element in an N×N matrix (rows and columns both sorted). Why can you treat each row as one of the K input lists for K-Way Merge?

   • A) Because each row is sorted independently, satisfying the pre-sorted input requirement
   • B) Because the matrix columns are also sorted, so row order does not matter
   • C) Because all elements in the matrix are distinct Correct Answer: A — Each row is a sorted sequence by definition of the problem. K-Way Merge requires K sorted inputs; treating each row as one list satisfies that requirement. Column sort order is a bonus that enables the O(K log K) binary-search alternative, but it is not needed for the heap approach.

4. Open-ended challenge: Apache Hadoop sets mapreduce.task.io.sort.factor = 10 by default, meaning it merges at most 10 sorted files at a time. If a mapper produces 100 spill files, Hadoop needs two rounds of merging (10 → 1 per round, then another pass). How would you calculate the optimal value of this factor to minimize total I/O bytes written to disk during the merge phase, assuming each merge pass writes N bytes? Is there a closed-form optimum, or does it depend on the number of spill files? There is no single correct answer.

---

🔗 Related Posts

• Two Heaps Pattern
• Top K Elements Pattern
• Backtracking Explained

---