Tournament Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Tournament Sort

An educational predecessor of Heapsort: finds the minimum element of the remaining unsorted range using a binary tournament tree of comparisons, swapping the champion to the sorted list.

How it works

Tournament Sort is a variation of Selection Sort. Instead of scanning the entire remaining unsorted list linearly in \(O(n)\) time to find the minimum, it structures comparisons as a binary tournament tree to find the minimum in \(O(\log n)\) time:

1. **Tree Construction:** Build a complete binary tree where the leaf nodes represent the unsorted elements of the array.
2. **First Tournament (Selection):**
   • Compare adjacent leaf nodes (matchups). The smaller element (the winner) moves up to the parent node.
   • Compare the parent winners level by level until the overall winner (minimum element) reaches the root node.
3. **Direct Output Swap:** Swap the root winner into its correct final sorted position.
4. **Update Tree:** Replace the winning leaf node's value with infinity (so it cannot win again) and rebuild the path from that leaf node up to the root, which requires only \(O(\log n)\) comparisons.
5. **Repeat:** Repeat the tournament update until all elements are sorted.

Complexity

Interactive visualization

Pseudocode

procedure tournamentSort(A):
  tree ← buildTournamentTree(A)
  n ← length(A)
  
  for i from 0 to n - 1:
    A[i] ← getWinner(tree)
    winnerIndex ← getWinnerLeafIndex(tree)
    updateLeafValue(tree, winnerIndex, INFINITY)
    rebuildPathToRoot(tree, winnerIndex)

JavaScript implementation

// Conceptual representation of Tournament Sort matches
function tournamentSort(arr) {
  const n = arr.length;
  const sorted = [];
  
  const tree = Array(2 * n).fill(Infinity);
  // Fill leaves
  for (let i = 0; i < n; i++) tree[n + i] = { val: arr[i], idx: i };
  
  // Build initial tree
  for (let i = n - 1; i > 0; i--) {
    tree[i] = (tree[2 * i].val <= tree[2 * i + 1].val) ? tree[2 * i] : tree[2 * i + 1];
  }
  
  for (let step = 0; step < n; step++) {
    const winner = tree[1];
    sorted.push(winner.val);
    
    // Replace leaf with infinity
    let curr = n + winner.idx;
    tree[curr] = { val: Infinity, idx: winner.idx };
    
    // Rebuild tree path
    while (curr > 1) {
      const parent = Math.floor(curr / 2);
      const sib = (curr % 2 === 0) ? curr + 1 : curr - 1;
      tree[parent] = (tree[curr].val <= tree[sib].val) ? tree[curr] : tree[sib];
      curr = parent;
    }
  }
  
  for (let i = 0; i < n; i++) arr[i] = sorted[i];
  return arr;
}

Pros and cons

When (not) to use it

• Theoretical exploration: Recommended for studying binary tree priority structures and tournament matching systems.
• Standard usage: Avoid; use Heapsort or Timsort, which do not allocate auxiliary nodes.