External Memory Sorting: K-Way Merge & Replacement Selection

The Aggarwal-Vitter External-Memory (DAM) Model

In the Disk Access Machine (DAM) model (Aggarwal & Vitter, 1988), the system has:

• $N$: Total number of records to sort (stored on external disk/NVMe).
• $M$: Number of records that fit in fast internal memory (RAM).
• $B$: Number of records transferred in a single contiguous block I/O ($1 \le B \le M/2$, e.g., a $4\text{ KB}$ or $64\text{ KB}$ page).

The cost metric is purely the number of block I/O transfers between disk and RAM. Notice why naive binary Merge Sort is disastrous here: a 2-way Merge Sort performs $\log_2(N/M)$ merge passes over the entire file, costing $2\frac{N}{B}\log_2\!\left(\frac{N}{M}\right)$ block I/Os. Instead, by allocating $K = \lfloor M / B \rfloor - 1$ input block buffers ($1$ block buffer per sorted run) and $1$ output block buffer in RAM, $K$-Way External Merge Sort merges $K = \Theta(M/B)$ runs in a single pass—shrinking the logarithm base from $2$ to $M/B$!

Why Tournament Loser Trees Beat Binary Heaps in $K$-Way Merging

When merging $K$ sorted runs, every step extracts the global minimum from run $r^*$ and replaces it with the next key from run $r^*$. In a standard binary min-heap, sifting the replacement element down requires comparing the two children against each other and then against the parent—$2 \log_2 K$ comparisons per element.

In Knuth's Tournament Loser Tree, the $K$ current run heads sit at the leaves of a complete binary tree, while each internal node stores the loser of the match played at that node (and the overall winner is stored in tree[0] above the root). When the winner from leaf $r^*$ is replaced by a new element, we walk strictly upward from leaf $r^*$ to the root: at each ancestor node, the previous winner of the other subtree is already sitting right there as the stored loser! Thus we perform exactly $1$ comparison per level ($log_2 K$ total) and never touch sibling nodes in memory.

Production C++20 Implementation: Tournament Loser Tree $K$-Way Merger & Replacement Selection

#include <concepts>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

// Tournament Loser Tree for K-Way Merging in exactly ceil(log2 K) comparisons per output
template <std::totally_ordered T>
class LoserTree {
public:
    explicit LoserTree(const std::vector<T>& initial_heads, T sentinel_max)
        : k_(1), sentinel_(sentinel_max) {
        while (k_ < initial_heads.size()) k_ <<= 1;
        keys_.assign(k_, sentinel_);
        for (std::size_t i = 0; i < initial_heads.size(); ++i) {
            keys_[i] = initial_heads[i];
        }
        tree_.assign(k_, 0);
        // Initialize by replaying matches from all leaves
        std::vector<std::size_t> winners(2 * k_, 0);
        for (std::size_t i = 0; i < k_; ++i) winners[k_ + i] = i;
        for (std::size_t p = k_ - 1; p >= 1; --p) {
            std::size_t left_w  = winners[2 * p];
            std::size_t right_w = winners[2 * p + 1];
            if (keys_[right_w] < keys_[left_w]) {
                tree_[p]   = left_w;  // Loser stays in tree_[p]
                winners[p] = right_w; // Winner advances
            } else {
                tree_[p]   = right_w;
                winners[p] = left_w;
            }
        }
        tree_[0] = winners[1]; // Overall champion stored at tree_[0]
    }

    std::size_t winner_run() const noexcept { return tree_[0]; }
    const T& winner_key() const noexcept { return keys_[tree_[0]]; }

    // Replace the head of the winning run and replay up to root in log2(K) comparisons
    void replay(std::size_t run_idx, T next_key) noexcept {
        keys_[run_idx] = std::move(next_key);
        std::size_t champ = run_idx;
        for (std::size_t p = (k_ + run_idx) >> 1; p >= 1; p >>= 1) {
            // If current champ is larger than the stored loser at tree_[p], they swap roles!
            if (keys_[tree_[p]] < keys_[champ]) {
                std::swap(champ, tree_[p]);
            }
        }
        tree_[0] = champ;
    }

private:
    std::size_t k_;
    T sentinel_;
    std::vector<T> keys_;
    std::vector<std::size_t> tree_; // tree_[0] = overall winner, tree_[1..k-1] = internal losers
};

// Multi-way merge of K sorted vectors using LoserTree
template <std::totally_ordered T>
std::vector<T> k_way_merge(const std::vector<std::vector<T>>& runs, T sentinel_max) {
    const std::size_t k = runs.size();
    if (k == 0) return {};

    std::vector<std::size_t> pos(k, 0);
    std::vector<T> heads(k, sentinel_max);
    std::size_t total = 0;
    for (std::size_t r = 0; r < k; ++r) {
        total += runs[r].size();
        if (!runs[r].empty()) heads[r] = runs[r][0];
    }

    LoserTree<T> lt(heads, sentinel_max);
    std::vector<T> out;
    out.reserve(total);

    for (std::size_t step = 0; step < total; ++step) {
        const std::size_t r = lt.winner_run();
        out.push_back(lt.winner_key());
        ++pos[r];
        T next_val = (pos[r] < runs[r].size()) ? runs[r][pos[r]] : sentinel_max;
        lt.replay(r, std::move(next_val));
    }
    return out;
}