K-Way Merge

K-Way Merge

You have k sorted sequences (lists, arrays, files, streams from different servers) and need to combine them into one sorted sequence, or find the smallest items across all of them. The k-way merge pattern keeps a min-heap holding the current front element of each sequence. The heap's top is always the globally smallest remaining element. Take it, then push the next element from the same sequence it came from.

Each step costs O(log k), because the heap never holds more than k items. For n elements in total, merging takes O(n log k), compared with O(n log n) for dumping everything into one array and sorting, or O(n·k) for scanning all k fronts every step.

lists:   [1, 4, 7]   [2, 5, 8]   [3, 6, 9]
heap:    {1, 2, 3}         → take 1, push 4 (its successor)
heap:    {2, 3, 4}         → take 2, push 5
...                        output: 1 2 3 4 5 6 7 8 9

Merge k sorted linked lists

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) if (head != null) heap.add(head);   // one entry per list: its front

    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode smallest = heap.poll();
        tail.next = smallest;                          // reuse the node: no copying
        tail = smallest;
        if (smallest.next != null) heap.add(smallest.next);   // replace with its successor
    }
    return dummy.next;
}

O(n log k) time, O(k) extra space. Two details matter:

• Skip null lists when seeding the heap. Empty inputs are a classic edge case.
• Use Comparator.comparingInt (or Integer.compare), not (a, b) -> a.val - b.val. Subtraction overflows for extreme values and silently breaks the ordering.

The alternative: divide and conquer

Merge the lists in pairs: list 1 with 2, 3 with 4, and so on. That halves the count each round, and repeating gives log k rounds, each touching all n nodes, so also O(n log k), with O(1) extra space for iterative merging (or O(log k) with recursion). Mention it as the heap-free option.

What doesn't work well is merging one list at a time into a growing result: it's O(n·k), because early elements get re-scanned in every merge.

Merge k sorted arrays

With arrays, a heap entry must remember where it came from: {value, arrayIndex, elementIndex}. This triple is the general template for every k-way merge problem.

public int[] mergeArrays(int[][] arrays) {
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
    int total = 0;
    for (int i = 0; i < arrays.length; i++) {
        total += arrays[i].length;
        if (arrays[i].length > 0) heap.add(new int[]{arrays[i][0], i, 0});
    }
    int[] out = new int[total];
    int pos = 0;
    while (!heap.isEmpty()) {
        int[] e = heap.poll();
        out[pos++] = e[0];
        int arr = e[1], next = e[2] + 1;
        if (next < arrays[arr].length) heap.add(new int[]{arrays[arr][next], arr, next});
    }
    return out;
}

K-th smallest across k sorted lists (or a sorted matrix)

Run the same loop, but stop after popping k elements. The k-th pop is the answer: O(k log m) for m lists, and you never merge everything.

Kth Smallest Element in a Sorted Matrix (rows and columns sorted) is the same problem: treat each row as a sorted list. An alternative is to binary search on the value range, counting how many elements are ≤ mid in O(n) per step using the sorted structure. That's O(n log(max − min)) time and O(1) space, and interviewers often ask about it as a follow-up.

Smallest range covering all k lists

Keep one element from every list in the heap, and track the current maximum among them. The range [heap min, current max] then always covers all lists. To try to shrink it, advance the list that holds the minimum. You can't shrink from the max side without dropping a list. Stop when any list runs out.

public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));   // {value, list, index}
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.size(); i++) {
        int v = nums.get(i).get(0);
        heap.add(new int[]{v, i, 0});
        max = Math.max(max, v);
    }
    int bestLo = 0, bestHi = Integer.MAX_VALUE;
    while (true) {
        int[] e = heap.poll();                                   // current minimum
        if ((long) max - e[0] < (long) bestHi - bestLo) { bestLo = e[0]; bestHi = max; }
        int list = e[1], next = e[2] + 1;
        if (next == nums.get(list).size()) break;               // this list is exhausted: can't cover it anymore
        int v = nums.get(list).get(next);
        heap.add(new int[]{v, list, next});
        max = Math.max(max, v);
    }
    return new int[]{bestLo, bestHi};
}

O(n log k). This is the pattern's hardest common variant: the heap gives the minimum, and a separate variable tracks the maximum.

Find k pairs with the smallest sums

Picture each row i as a sorted list of pairs (a[i], b[0]), (a[i], b[1]), … Seed the heap with (i, 0) for the first k rows, and each time you pop (i, j), push (i, j+1). That's O(k log k), and it never generates all m × n pairs.

Where it's used outside interviews

• External merge sort: sort chunks of a file too big for memory, write each chunk to disk, then k-way merge the sorted chunks by streaming them. This is how databases and big-data systems sort huge datasets.
• LSM-tree storage engines (Cassandra, RocksDB, LevelDB) merge sorted files during compaction.
• Search engines merge sorted posting lists. Distributed queries merge sorted partial results from many shards.

Follow-up questions this topic invites — and their answers

Q: Why is the complexity O(n log k) and not O(n log n)? A: The heap holds at most k elements (one per source), so each insert and removal costs O(log k), and each of the n elements goes through the heap exactly once.

Q: Heap or divide-and-conquer for merging k lists? A: Both are O(n log k). The heap processes elements in a single streaming pass, which is good for data arriving from files or network streams. Pairwise merging needs no heap and O(1) extra space for linked lists, but makes log k passes over the data.

Q: How would you merge sorted files that don't fit in memory? A: Open a buffered reader for each file, seed a min-heap with each file's first record, then repeatedly write the smallest to the output and refill from that file. Memory is O(k × buffer size) regardless of file sizes. If k is huge, merge in multiple passes (for example 100 files at a time).

Q: What must a heap entry contain? A: The value used for ordering, plus enough information to fetch that source's next element: the list node itself (which knows next), or the source index plus the position within it.

Q: How do you handle duplicate values across lists? A: Nothing special is needed for merging: equal values come out adjacent. If the output must be distinct, skip any value equal to the last one written. For "smallest range", duplicates are fine, and the logic still holds.