The Tournament Tree

A tournament tree, also called a selection tree, is a complete binary tree over k fixed leaf slots. Each leaf holds the current candidate from one input, and each internal node holds the winner of the match between its two children under the ordering in use. The root holds the overall winner, so reading the minimum of k streams costs O(1).

Building the tree from k filled leaves costs k − 1 comparisons, one per internal node, which is optimal for finding a minimum. Like a binary heap, the tree is complete and can live in an array with index arithmetic; unlike a heap, the leaf set is fixed and the internal nodes hold copies or references rather than elements of their own.

The structure earns its keep on the update. When the winner is consumed, its source supplies a replacement into that same leaf, and only the matches on the path from that leaf to the root can change outcome — every other match involved neither the departing element nor the arriving one.

Replaying that path is ⌈log₂ k⌉ matches. No other node is read or written, and the tree's shape never changes, so the update touches a fixed set of array positions determined by the leaf index. The output stream is produced one element at a time with a logarithmic number of comparisons each, and the tree's size stays exactly 2k − 1 nodes regardless of how much data flows through it.

Replaying a match in a winner tree requires reading both children, because the node's own value is one of the two contenders and the other must be fetched. Demuth's 1956 refinement, the loser tree, stores at each internal node the loser of that match and keeps the overall winner in a separate slot above the root.

Now the ascent carries the current winner in a register and compares it against one stored loser per level. Each level is one comparison and one memory read, and when the incumbent loses, the two values swap in place and the ascent continues with the new winner. The comparison count is unchanged at ⌈log₂ k⌉, but memory traffic is halved, which is why external sorting implementations use loser trees rather than winner trees.

To merge k sorted runs, load the first element of each run into a leaf, build the tree, then repeat: emit the root, pull the next element from the run that supplied it, and replay that leaf's path. Each of the n output elements costs ⌈log₂ k⌉ comparisons, giving O(n log k) total.

The alternative is repeated two-way merging, which passes over the data log₂ k times and reads every element once per pass. The tournament tree does the same number of comparisons in a single pass, which is what matters when the runs live on disk or across a network: the merge becomes one sequential scan of each run with O(k) resident state. This is the merge step that makes external sorting and LSM tree compaction linear in the data.

A binary heap of k run heads solves the same problem. Its extract-min followed by an insertion of the replacement sifts a value down from the root, and each level of that descent costs two comparisons: one to select the smaller child, one to test the sifted value against it. That is about 2 log₂ k comparisons per output element.

A loser tree ascends instead of descending, and an ascent already knows its opponent, so it needs one comparison per level. For a 1,000-way merge the difference is roughly 10 comparisons per record against 20. When keys are long strings or multi-column tuples, that ratio is the ratio of merge times. The heap's advantage is that k can change at will, while the tournament tree's leaf count is fixed when the tree is built.

Tournament trees also generate the runs they later merge. Fill the tree with M records from the unsorted input, then repeatedly emit the winner and read one new record into its leaf. If the new record's key is at least the key just emitted it belongs to the current run; if it is smaller it cannot be output in sorted order now, so it is tagged for the next run and treated as losing every match in this one.

The current run ends when every leaf carries a next-run tag. Because records arriving after the current output position stay usable, runs grow past the memory that holds them: for random input the expected run length is 2M rather than M. Halving the run count removes work from the merge phase, and on input that is already close to sorted a single run can absorb the entire file.

The tournament also answers a selection question. Finding the smallest of n elements takes n − 1 comparisons, and the second-smallest must have lost exactly one match — its only loss was to the winner. The candidates are therefore the ⌈log₂ n⌉ elements that met the winner on its path, not all n − 1 losers.

A second tournament among those gives the second-smallest in n + ⌈log₂ n⌉ − 2 comparisons, which Kislitsyn proved optimal. The record of who lost to whom is information the tournament produces for free and a heap discards.

When a run is exhausted its leaf has nothing to supply. The standard treatment writes a sentinel key that loses every comparison — positive infinity for a min-tournament — so the leaf stays in the tree and the path arithmetic never changes. The merge stops when the winner is a sentinel, meaning every run is drained.

Sentinels keep k fixed, which is the point: a tournament tree cannot cheaply shrink, because removing a leaf changes the shape and invalidates every index. Ties need equal care. Comparing on the key alone leaves the winner ambiguous; breaking ties by run number, with lower-numbered runs winning, makes the merge stable when the runs were produced in order.

Both variants live in an array of 2k − 1 nodes, addressed by index arithmetic, and the internal nodes usually hold a run index plus a cached key rather than a whole record. The cached key avoids dereferencing a record on every comparison, which matters when the records are large or paged from disk.

The access pattern is a fixed root-to-leaf path per output element, so the top levels stay in cache and only the deep nodes miss. Since only the levels above one leaf are touched, the working set for a merge is the tree plus one input buffer per run — not the runs themselves — and k is bounded in practice by how many buffers fit in memory rather than by the tree.

A tournament tree gives one comparison per level instead of two, a fixed 2k − 1 node footprint, no allocation after construction, and a completely predictable access pattern. For merging a known number of sorted streams it does strictly less work than a heap.

It is also less general. The leaf count is fixed at build time, so inserting a new stream means rebuilding; there is no decrease-key, no meld, and no way to remove an arbitrary element. Exhausted inputs must be padded with sentinels rather than dropped, so a merge with many short runs keeps paying for dead leaves. Workloads that need a dynamic queue want a priority queue; workloads that need to combine queues want a pairing heap.

Database sort operators are the documented home of the structure. Graefe's survey of sorting in database systems specifies the tree-of-losers priority queue for both phases of external merge sort — run generation by replacement selection and the merge itself — on the grounds that it reaches a new winner in log₂ N comparisons and supports near-optimal comparison counts across the whole sort. IBM has patented hardware sort accelerators built directly on the tournament tree, including designs that stream keys through a tournament tree backed by external memory and ones that address the cache misses replacement selection causes.

Where systems merge sorted runs without a tournament tree, they use a heap for the same job, which makes the comparison concrete: RocksDB's MergingIterator keeps one child iterator per memtable and SST file in a binary heap keyed on current key, and PostgreSQL's tuplesort.c merges external run tapes through a heap of tape heads. Both perform the two-comparisons-per-level descent that a loser tree avoids.

A tournament tree is a complete binary tree over a fixed set of k inputs that caches the outcome of every match. Consuming the winner and replacing its leaf invalidates only one root-to-leaf path, so the next winner emerges in ⌈log₂ k⌉ comparisons. Storing losers instead of winners halves the memory traffic of that ascent.

Merging n elements from k runs costs O(n log k) with 2k − 1 nodes of state, and replacement selection uses the same tree to produce runs averaging twice the size of memory. The structure cannot resize, meld, or delete arbitrary elements: it trades every dynamic operation for the cheapest possible repeated selection over a fixed set of streams.