K-Way Merge

August 2026 · 21 min read

You have k sorted sequences and want one sorted sequence. This is the operation behind external sorting, LSM-tree compaction in every modern key-value store, merging sorted index segments in a search engine, and the Merge k Sorted Lists interview question. The heap solution is a textbook example of using a data structure to turn a repeated linear scan into a logarithmic one.

The Idea

At every step the next output element is the smallest among the current fronts of the k sequences. Everything behind a front is larger than it, so only the fronts can compete.

The naive method scans all k fronts each time: O(k) per output element, O(Nk) overall for N total elements. A min-heap holding exactly those k fronts answers the same question in O(log k), giving O(N log k).

The heap therefore holds one entry per sequence, not per element. Its size never exceeds k no matter how large the inputs are — which is what makes this work on data far larger than memory.

push the first element of every non-empty sequence into a min-heap
while heap is not empty:
    (value, which_sequence) = heap.pop()
    emit value
    if that sequence has a next element:
        heap.push(next value, which_sequence)

Merge k Sorted Lists

The linked-list formulation, which is the version usually asked:

#include <queue>
#include <vector>

struct ListNode { int val; ListNode* next; };

struct Greater {
    bool operator()(const ListNode* a, const ListNode* b) const {
        return a->val > b->val;               // '>' gives a MIN-heap
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, Greater> heap;

    for (ListNode* head : lists)
        if (head) heap.push(head);             // skip empty lists

    ListNode dummy{0, nullptr};                // sentinel: no special case for the first node
    ListNode* tail = &dummy;

    while (!heap.empty()) {
        ListNode* node = heap.top();
        heap.pop();
        tail->next = node;                     // splice, do not copy
        tail = node;
        if (node->next) heap.push(node->next);
    }

    tail->next = nullptr;
    return dummy.next;
}

Three details that matter. The dummy sentinel removes the “is this the first output node” branch entirely — the same trick the linked list series leans on. Empty lists must be filtered before the initial pushes, or you dereference null immediately. And nodes are spliced, not copied, so the merge allocates nothing.

Complexity

Note that log k beats log N substantially when k is small and the sequences are long — merging 8 files of a million records each gives log2 8 = 3 versus log2(8 × 106) ≈ 23.

Sequential merging is the trap. Merging list 1 with list 2, then that result with list 3, and so on re-walks the accumulated prefix every time. The first list is traversed k-1 times, and the total is O(Nk). It looks natural and is asymptotically much worse.

The Real Application: External Sorting

This is where k-way merge stops being an exercise. To sort 500 GB with 8 GB of RAM:

1. Run generation. Read 8 GB at a time, sort it in memory, write it out as a sorted run. You end up with ~64 sorted files.
2. Merge. Open all 64, read a buffer from each, and run a k-way merge with a heap of 64 entries, streaming the output to disk.

The heap holds 64 items regardless of the 500 GB flowing through it. Memory usage is dominated by the I/O buffers, not the algorithm. Every database's ORDER BY on a large table does exactly this, as does the classic Unix sort utility.

The same structure drives LSM-tree compaction in RocksDB, LevelDB, Cassandra and friends: several sorted SSTables are merged into one, with the heap picking the winning key at each step and duplicate keys resolved by preferring the newest source.

A Harder Variant: Smallest Range Covering All Lists

Given k sorted lists, find the smallest range [lo, hi] containing at least one element from each. The k-way merge machinery solves it almost unchanged.

Keep the heap of k fronts, and separately track the maximum among those fronts. The current window is [heap.top(), current_max], and by construction it contains one element from every list. Advancing the minimum is the only move that can shrink the window:

std::vector<int> smallestRange(std::vector<std::vector<int>>& lists) {
    using Item = std::tuple<int, int, int>;          // (value, list index, position)
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> heap;

    int curMax = INT_MIN;
    for (int i = 0; i < (int)lists.size(); ++i) {
        if (lists[i].empty()) return {};
        heap.push({lists[i][0], i, 0});
        curMax = std::max(curMax, lists[i][0]);
    }

    int bestLo = 0, bestHi = INT_MAX;
    while (true) {
        auto [val, li, pos] = heap.top();
        heap.pop();

        if (curMax - val < bestHi - bestLo) { bestLo = val; bestHi = curMax; }

        if (pos + 1 == (int)lists[li].size()) break;  // a list is exhausted: stop
        int nxt = lists[li][pos + 1];
        curMax = std::max(curMax, nxt);
        heap.push({nxt, li, pos + 1});
    }
    return {bestLo, bestHi};
}

The loop must stop the instant any list runs out — from then on no window can cover all k lists, so nothing further can improve the answer.

Practice

• Merge k Sorted Lists hard — the canonical problem; implement both the heap and the divide-and-conquer version.
• Kth Smallest Element in a Sorted Matrix medium — each row is a sorted list; merge and stop at k.
• Find K Pairs with Smallest Sums medium — k virtual lists, one per element of the first array.
• Smallest Range Covering Elements from K Lists hard — the variant above.
• Merge Sorted Array easy — the k = 2 base case, worth doing backwards and in place.