Tournament Merge Sort

Tournament merge sort uses a tournament tree to merge sorted sequences. Each element competes in a structured tree, and the winner at the root is the smallest element. After removing the winner, the tree is updated to find the next smallest.

It is conceptually similar to multiway merge, but uses a tournament structure instead of a heap.

Problem

Given an array $A$ of length $n$, reorder it such that:

$$ A[0] \le A[1] \le \dots \le A[n-1] $$

Idea

Build a tournament tree:

leaves represent elements or input streams
internal nodes store the winner of comparisons
the root stores the global minimum

After extracting the minimum:

replace it with the next element from the same source
update the path to the root

This maintains the tournament property.

Algorithm

tournament_merge_sort(A):
    split A into k sorted runs

    build tournament tree over runs

    result = []

    while tree not empty:
        min_element = root value
        append to result

        replace leaf with next element from that run
        update tree

    return result

Tree update:

update_tree(node):
    while node has parent:
        recompute winner at parent
        move upward

Example

Let sorted runs:

[1, 4, 7]
[2, 5, 8]
[3, 6, 9]

Initial tournament:

match	winner
1 vs 2	1
3 vs winner	1

Extract 1, replace with 4, update tree.

Repeat:

Final result:

$$ [1,2,3,4,5,6,7,8,9] $$

Correctness

The tournament tree ensures that the smallest element among all current candidates is at the root. Each update maintains this invariant. Extracting elements in this order produces a sorted sequence.

Complexity

metric	value
build tree	$O(k)$
each extraction	$O(\log k)$
total merge	$O(n \log k)$

Total sort:

$$ O(n \log n) $$

Space:

$$ O(k) $$

Properties

property	value
stable	yes with careful handling
in-place	no
merge structure	tournament tree
comparison reuse	efficient

Notes

Tournament merge sort reduces repeated comparisons by reusing previous comparison results stored in the tree.

It is closely related to:

winner trees
loser trees

These structures are widely used in external sorting and database systems.

Implementation

def tournament_merge_sort(runs):
    import math

    k = len(runs)
    indices = [0] * k

    # build tree as array
    size = 1
    while size < k:
        size *= 2

    tree = [None] * (2 * size)

    def get_value(i):
        if i >= k or indices[i] >= len(runs[i]):
            return float("inf")
        return runs[i][indices[i]]

    # initialize leaves
    for i in range(size):
        tree[size + i] = i

    # build tree
    for i in range(size - 1, 0, -1):
        left = tree[2 * i]
        right = tree[2 * i + 1]

        if get_value(left) <= get_value(right):
            tree[i] = left
        else:
            tree[i] = right

    result = []

    while True:
        winner = tree[1]
        val = get_value(winner)

        if val == float("inf"):
            break

        result.append(val)
        indices[winner] += 1

        # update path
        i = size + winner
        while i > 1:
            i //= 2
            left = tree[2 * i]
            right = tree[2 * i + 1]

            if get_value(left) <= get_value(right):
                tree[i] = left
            else:
                tree[i] = right

    return result