K Way Winner Tree Merge

K way winner tree merge is a tournament-tree method for merging multiple sorted streams. Each leaf represents one input stream, and each internal node stores the winner of a comparison between its children.

The winner is usually the smallest current element among the competing streams. After the winner is emitted, only the path from that stream’s leaf to the root must be recomputed.

Problem

Given $k$ sorted streams, merge them into one sorted output.

The input streams may be sorted runs on disk, sorted partitions in memory, or streams produced by earlier merge phases.

Core Idea

Build a binary tournament tree:

• leaves hold current stream heads
• internal nodes hold the winner among their children
• the root holds the global winner

After outputting the root element, advance that stream and replay the tournament along its path to the root.

Algorithm

winner_tree_merge(streams):
    read first element from each stream
    build winner tree

    while root is not exhausted:
        i = stream index stored at root
        output current value from stream i

        advance stream i
        update path from leaf i to root

The update is local. All comparisons outside the winner path remain valid because their input values did not change.

Example

Merge four streams:

Initial winners:

The root holds A with value 1. Emit 1, advance A to 5, and update the path involving A.

The emitted order is:

Correctness

Each leaf holds the smallest unmerged element from its stream. Since each stream is sorted, no later element in a stream can be smaller than its current head.

Each internal node stores the smaller current head among the leaves in its subtree. By induction over the tree height, the root stores the smallest current head among all streams.

After emitting the root value, only one leaf changes. Updating the nodes on that leaf’s path restores the same invariant. Repeating this process emits all elements in sorted order.

Complexity

Let:

• $N$ be the total number of elements
• $k$ be the number of streams

Building the tree costs:

Each output updates a path of height:

Total time:

Space usage:

Winner Tree vs Loser Tree

Both structures support efficient k-way merge. Winner trees are conceptually direct: every internal node says which child currently wins.

When to Use

Use winner tree merge when:

• many sorted runs must be merged
• predictable $O(\log k)$ update time is needed
• a heap feels too general
• a tournament representation is easier to tune
• you need a clear merge primitive for external sorting

Loser trees are often preferred in optimized systems, but winner trees are a useful baseline and easier to implement correctly.

Implementation Sketch

class WinnerTree:
    def __init__(self, streams):
        self.streams = [iter(s) for s in streams]
        self.k = len(streams)
        self.keys = [None] * self.k
        self.tree = [-1] * (2 * self.k)

        for i in range(self.k):
            self._advance(i)

        for i in range(self.k):
            self.tree[self.k + i] = i

        for p in range(self.k - 1, 0, -1):
            self.tree[p] = self._winner(self.tree[2 * p], self.tree[2 * p + 1])

    def _advance(self, i):
        try:
            self.keys[i] = next(self.streams[i])
        except StopIteration:
            self.keys[i] = float("inf")

    def _winner(self, i, j):
        if i == -1:
            return j
        if j == -1:
            return i
        if self.keys[i] <= self.keys[j]:
            return i
        return j

    def pop(self):
        winner = self.tree[1]
        value = self.keys[winner]

        if value == float("inf"):
            raise StopIteration

        self._advance(winner)

        p = (self.k + winner) // 2
        while p >= 1:
            self.tree[p] = self._winner(self.tree[2 * p], self.tree[2 * p + 1])
            p //= 2

        return value

def winner_tree_merge(streams):
    tree = WinnerTree(streams)
    out = []

    while True:
        try:
            out.append(tree.pop())
        except StopIteration:
            break

    return out

Notes

Winner tree merge is the natural tournament-tree form of k-way merge. It has the same asymptotic cost as heap merge, but its structure makes the update path explicit and predictable.