# Tournament Merge Sort

# 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:

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

This maintains the tournament property.

## Algorithm

```text id="k3m8xp"
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:

```text id="p7v2qn"
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

```python id="k9s2xp"
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
```