Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Tournament trees: merge sorted runs through one winner path

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A tournament merge tree places one current head from each sorted run at a leaf. Each internal node stores the run ID of the smaller head in its two children. When the root winner is emitted, only that run advances; the leaf changes and winners are recomputed on its path to the root. Empty runs have no contender. The example uses the run ID to break equal-value ties, so equal keys from two runs have stable source order. The entire runs are copied into Python lists for clarity; an external merge would buffer heads from files instead. This is a winner tree, not a loser tree, because internal nodes retain winners.

Operational case

Four runs contain [19,47,83], [29,47,61], an empty run, and [17,103]. The merged output starts with 17 from run three, then 19 from run zero; both 47 values retain run-zero-before-run-one tie order. After a run ends, its leaf becomes empty and cannot win again. The tree's padded leaves let the run count be any positive integer rather than only a power of two. If one input run is unsorted, updating just the winner path cannot repair global sorted order, so construction rejects it.

Working Python program

python
class TournamentMerge:
    def __init__(self, sorted_runs):
        self.runs = [list(run) for run in sorted_runs]
        if any(run != sorted(run) for run in self.runs):
            raise ValueError("each input run must be sorted")
        self.count = len(self.runs)
        self.base = 1
        while self.base < max(1, self.count):
            self.base *= 2
        self.positions = [0] * self.count
        self.winners = [None] * (2 * self.base)
        for run_id, run in enumerate(self.runs):
            if run:
                self.winners[self.base + run_id] = run_id
        for position in range(self.base - 1, 0, -1):
            self.winners[position] = self._better(self.winners[2 * position], self.winners[2 * position + 1])

    def _better(self, first, second):
        if first is None:
            return second
        if second is None:
            return first
        first_key = (self.runs[first][self.positions[first]], first)
        second_key = (self.runs[second][self.positions[second]], second)
        return first if first_key <= second_key else second

    def pop(self):
        winner = self.winners[1]
        if winner is None:
            raise IndexError("all runs exhausted")
        value = self.runs[winner][self.positions[winner]]
        self.positions[winner] += 1
        leaf = self.base + winner
        if self.positions[winner] == len(self.runs[winner]):
            self.winners[leaf] = None
        while leaf > 1:
            leaf //= 2
            self.winners[leaf] = self._better(self.winners[2 * leaf], self.winners[2 * leaf + 1])
        return value, winner

    def drain(self):
        merged = []
        while self.winners[1] is not None:
            merged.append(self.pop())
        return merged


if __name__ == "__main__":
    merge = TournamentMerge([[19, 47, 83], [29, 47, 61], [], [17, 103]])
    print(merge.drain())

Output

Output
[(17, 3), (19, 0), (29, 1), (47, 0), (47, 1), (61, 1), (83, 0), (103, 3)]

Time, space, and tradeoff

With K runs and T total values, construction copies O(T) values and builds O(K) tree slots. Each emitted value updates O(log K) internal winners, giving O(T log K) merge time and O(K+T) memory in this in-memory version. A streaming version could retain O(K) heads plus source buffers instead of copying all T values. The tree stores contender IDs rather than moving values through every internal node. A binary heap offers the same asymptotic merge bound, while this tree gives a fixed replay path after each known source advances.

Common Mistakes

  • Do not call internal winner records loser-tree state.
  • Do not forget to remove an exhausted run from contention.
  • Do not claim sorted output if a source run violates its sorted-input contract.
  • Do not ignore tie ordering when a downstream consumer needs stable source order.

Connected lessons

Compare its query and update boundary with Fibonacci heaps: cut on decrease and consolidate on removal, Priority search trees: report events in a three-sided region, Reduced ordered decision diagrams: share identical rule branches, then complete the structure audit and decision quiz.

Huffman trees: assign prefix codes from symbol frequencies adds a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details