Tournament Sort

Selection

Sorts by repeatedly finding the minimum element and placing it at the beginning.

Tree

Constructs a tree data structure to organize elements, then traverses it to produce a sorted sequence.

Out-of-Place

Requires auxiliary memory proportional to the input size (O(n)).

Stable

Preserves the relative order of elements with equal values.

A tournament tree records the smaller competitor at each internal node. After outputting the champion, only its path to the root must be replayed.

Visualize Fullscreen

Demo

20 elements • 4x Speed

tournament ● Active ● Sorted

Nodes appear as the algorithm builds its structure.

Did you know?

After removing the champion, only matches on that leaf’s path to the root need to be replayed.
Ties go to the earlier input position in this winner tree, preserving the order of equal values.
The original values stay in a separate copy while winner-tree leaves are retired one by one. That prevents writing sorted output over a competitor that still needs to play another match.

How it Works

Build a complete winner tree over input positions.
Output the winner at its root.
Remove its leaf and replay matches along that leaf’s path.

Complexity Analysis

Best Case

O(n \log n)

Average

O(n \log n)

Worst Case

O(n \log n)

Space

O(n)

Advantages

O(n log n) comparisons.
Ties can be resolved by input order.

Disadvantages

Needs O(n) extra memory for its tree and input copy.

Implementation

JavaScript tournament-sort.js

function tournamentSort(a) {
  const source = [...a], n = a.length;
  let size = 1; while (size < n) size *= 2;
  const tree = Array(2 * size).fill(-1);
  for (let i = 0; i < n; i++) tree[size + i] = i;
  const win = (x, y) => x < 0 ? y : y < 0 ? x : source[x] <= source[y] ? x : y;
  for (let i = size - 1; i > 0; i--) tree[i] = win(tree[2 * i], tree[2 * i + 1]);
  for (let out = 0; out < n; out++) {
    const index = tree[1]; a[out] = source[index];
    let node = size + index; tree[node] = -1;
    while (node > 1) { node = Math.floor(node / 2); tree[node] = win(tree[2 * node], tree[2 * node + 1]); }
  }
  return a;
}