# Tournament Sort

# Tournament Sort

Tournament sort selects elements by organizing comparisons as a tournament. Each leaf represents an input value. Internal nodes store the winner of comparing their children. For ascending order, the winner is the smaller value.

After the minimum is emitted, its leaf is replaced by infinity, and the path from that leaf to the root is recomputed. The next root gives the next smallest value.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

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

## Key Idea

A tournament tree lets the algorithm find the current minimum in $O(1)$ after the tree is built. Updating the tree after removing one element costs $O(\log n)$.

## Algorithm

```id="k7x2p4"
tournament_sort(A):
    build tournament tree from A

    result = empty list

    repeat n times:
        winner = tree.root
        append winner.value to result

        replace winner.leaf with infinity
        update path from winner.leaf to root

    return result
```

## Example

Let

$$
A = [7, 2, 5, 1]
$$

Initial tournament:

```id="m3q9x1"
        1
      /   \
     2     1
    / \   / \
   7   2 5   1
```

The first output is $1$. Replace its leaf with infinity and recompute the affected path. The next root becomes $2$, then $5$, then $7$.

Sorted result:

$$
[1, 2, 5, 7]
$$

## Correctness

The root of a min tournament tree always stores the minimum among all active leaves. After outputting that minimum, replacing its leaf with infinity removes exactly that element from future consideration. Recomputing the path to the root restores the tournament invariant. Repeating this process outputs the remaining elements in nondecreasing order.

## Complexity

| phase           |          time |
| --------------- | ------------: |
| build tree      |        $O(n)$ |
| each extraction |   $O(\log n)$ |
| all extractions | $O(n \log n)$ |

Total time:

$$
O(n \log n)
$$

Space complexity:

$$
O(n)
$$

## Properties

* comparison-based
* not in-place
* stable only with tie-breaking by original index
* related to heapsort and loser-tree merge
* useful when repeated minimum extraction is needed

## When to Use

Tournament sort is useful when the sorting process naturally fits repeated selection, especially in external sorting and multiway merging. For in-memory array sorting, heapsort gives a more compact implementation with similar asymptotic behavior.

## Implementation

```id="p8x3q2"
import math

def tournament_sort(a):
    n = len(a)
    if n == 0:
        return []

    size = 1
    while size < n:
        size *= 2

    tree = [(math.inf, -1)] * (2 * size)

    for i, value in enumerate(a):
        tree[size + i] = (value, i)

    for i in range(size - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])

    result = []

    for _ in range(n):
        value, original_index = tree[1]
        result.append(value)

        pos = size + original_index
        tree[pos] = (math.inf, original_index)

        pos //= 2
        while pos >= 1:
            tree[pos] = min(tree[2 * pos], tree[2 * pos + 1])
            pos //= 2

    return result
```

```id="z5k8v1"
type entry struct {
    value int
    index int
}

func less(a, b entry) bool {
    if a.value != b.value {
        return a.value < b.value
    }
    return a.index < b.index
}

func TournamentSort(a []int) []int {
    n := len(a)
    if n == 0 {
        return nil
    }

    size := 1
    for size < n {
        size *= 2
    }

    inf := int(^uint(0) >> 1)
    tree := make([]entry, 2*size)

    for i := range tree {
        tree[i] = entry{value: inf, index: i}
    }

    for i, v := range a {
        tree[size+i] = entry{value: v, index: i}
    }

    for i := size - 1; i >= 1; i-- {
        if less(tree[2*i], tree[2*i+1]) {
            tree[i] = tree[2*i]
        } else {
            tree[i] = tree[2*i+1]
        }
    }

    result := make([]int, 0, n)

    for i := 0; i < n; i++ {
        winner := tree[1]
        result = append(result, winner.value)

        pos := size + winner.index
        tree[pos] = entry{value: inf, index: winner.index}

        for pos /= 2; pos >= 1; pos /= 2 {
            if less(tree[2*pos], tree[2*pos+1]) {
                tree[pos] = tree[2*pos]
            } else {
                tree[pos] = tree[2*pos+1]
            }

            if pos == 1 {
                break
            }
        }
    }

    return result
}
```