Tournament Sort — VisualAlgorithms Docs

How it works

Builds a winner tree (a tournament bracket): adjacent players compete in rounds and the smaller value advances. The champion is output, its leaf is retired, and only the single path from that leaf back to the root is replayed in O(log n) before the next champion emerges.
Implementation

      
 function tournamentSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  let size = 1;
  while (size < n) size <<= 1;
  const values = new Array(size);
  for (let i = 0; i < n; i++) values[i] = arr[i];
  for (let i = n; i < size; i++) values[i] = Infinity;
  const tree = new Array(2 * size).fill(-1);
  for (let i = 0; i < size; i++) tree[size + i] = i;
  for (let node = size - 1; node >= 1; node--) {
    const left = tree[2 * node];
    const right = tree[2 * node + 1];
    tree[node] = values[left] <= values[right] ? left : right;
  }
  for (let out = 0; out < n; out++) {
    const winner = tree[1];
    const championValue = values[winner];
    arr[out] = championValue;
    write(out, championValue);
    markSorted(out);
    values[winner] = Infinity;
    let node = size + winner >> 1;
    while (node >= 1) {
      const left = tree[2 * node];
      const right = tree[2 * node + 1];
      tree[node] = values[left] <= values[right] ? left : right;
      node >>= 1;
    }
    checkpoint(out + 1, n);
  }
}
 def tournamentSort(arr, stats):
    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    size = 1
    while (size < n):
        size <<= 1
    values = [0] * size
    for i in range(n):
        values[i] = arr[i]
    for i in range(n, size):
        values[i] = float('inf')
    tree = [-1] * (2 * size)
    for i in range(size):
        tree[(size + i)] = i
    for node in range((size - 1), (1 - 1), -1):
        left = tree[(2 * node)]
        right = tree[((2 * node) + 1)]
        tree[node] = (left if (values[left] <= values[right]) else right)
    for out in range(n):
        winner = tree[1]
        championValue = values[winner]
        arr[out] = championValue
        write(out, championValue)
        markSorted(out)
        values[winner] = float('inf')
        node = ((size + winner) >> 1)
        while (node >= 1):
            left = tree[(2 * node)]
            right = tree[((2 * node) + 1)]
            tree[node] = (left if (values[left] <= values[right]) else right)
            node >>= 1
        checkpoint((out + 1), n)
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int size = 1;
    while((size < n)) {
        size <<= 1;
    }
    std::vector<int> values(size, 0);
    for(int i=0; i<n; i++) {
        values[i] = arr[i];
    }
    for(int i=n; i<size; i++) {
        values[i] = 2147483647;
    }
    std::vector<int> tree((2 * size), -1);
    for(int i=0; i<size; i++) {
        tree[(size + i)] = i;
    }
    for(int node=(size - 1); node>(1 - 1); node--) {
        int left = tree[(2 * node)];
        int right = tree[((2 * node) + 1)];
        tree[node] = (((values[left] <= values[right])) ? (left) : (right));
    }
    for(int out=0; out<n; out++) {
        int winner = tree[1];
        int championValue = values[winner];
        arr[out] = championValue;
        write(out, championValue);
        markSorted(out);
        values[winner] = 2147483647;
        int node = ((size + winner) >> 1);
        while((node >= 1)) {
            int left = tree[(2 * node)];
            int right = tree[((2 * node) + 1)];
            tree[node] = (((values[left] <= values[right])) ? (left) : (right));
            node >>= 1;
        }
        checkpoint((out + 1), n);
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int size = 1;
    while((size < n)) {
        size <<= 1;
    }
    int[] values = new int[size];
    for(int i=0; i<n; i++) {
        values[i] = arr[i];
    }
    for(int i=n; i<size; i++) {
        values[i] = int.MaxValue;
    }
    int[] tree = new int[(2 * size)];
    for(int _i=0;_i<(2 * size);_i++) tree[_i]=-1;
    for(int i=0; i<size; i++) {
        tree[(size + i)] = i;
    }
    for(int node=(size - 1); node>(1 - 1); node--) {
        int left = tree[(2 * node)];
        int right = tree[((2 * node) + 1)];
        tree[node] = (((values[left] <= values[right])) ? (left) : (right));
    }
    for(int out=0; out<n; out++) {
        int winner = tree[1];
        int championValue = values[winner];
        arr[out] = championValue;
        write(out, championValue);
        markSorted(out);
        values[winner] = int.MaxValue;
        int node = ((size + winner) >> 1);
        while((node >= 1)) {
            int left = tree[(2 * node)];
            int right = tree[((2 * node) + 1)];
            tree[node] = (((values[left] <= values[right])) ? (left) : (right));
            node >>= 1;
        }
        checkpoint((out + 1), n);
    }
} #include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int size = 1;
    while((size < n)) {
        size <<= 1;
    }
    int* values = (int*)malloc((size) * sizeof(int));
    for(int i=0; i<n; i++) {
        values[i] = arr[i];
    }
    for(int i=n; i<size; i++) {
        values[i] = 2147483647;
    }
    int* tree = (int*)malloc(((2 * size)) * sizeof(int)); for(int _i=0;_i<(2 * size);_i++) tree[_i]=-1;
    for(int i=0; i<size; i++) {
        tree[(size + i)] = i;
    }
    for(int node=(size - 1); node>(1 - 1); node--) {
        int left = tree[(2 * node)];
        int right = tree[((2 * node) + 1)];
        tree[node] = (((values[left] <= values[right])) ? (left) : (right));
    }
    for(int out=0; out<n; out++) {
        int winner = tree[1];
        int championValue = values[winner];
        arr[out] = championValue;
        write(out, championValue);
        markSorted(out);
        values[winner] = 2147483647;
        int node = ((size + winner) >> 1);
        while((node >= 1)) {
            int left = tree[(2 * node)];
            int right = tree[((2 * node) + 1)];
            tree[node] = (((values[left] <= values[right])) ? (left) : (right));
            node >>= 1;
        }
        checkpoint((out + 1), n);
    }
} 