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) {
  const n = arr.length;
  let size = 1;
  while (size < n) size <<= 1;                 // leaves = power of two
  const value = Array.from({ length: size }, (_, i) => i < n ? arr[i] : Infinity);
  const win = new Array(2 * size).fill(-1);    // win[node] = leaf index of subtree min
  for (let i = 0; i < size; i++) win[size + i] = i;
  // Build the bracket bottom-up: each parent holds its smaller child.
  for (let node = size - 1; node >= 1; node--) {
    const l = win[2 * node], r = win[2 * node + 1];
    win[node] = value[l] <= value[r] ? l : r;
  }
  for (let out = 0; out < n; out++) {
    const champ = win[1];                       // champion = current minimum
    arr[out] = value[champ];
    value[champ] = Infinity;                    // retire that leaf
    // Replay only the path from the retired leaf to the root: O(log n).
    for (let node = (size + champ) >> 1; node >= 1; node >>= 1) {
      const l = win[2 * node], r = win[2 * node + 1];
      win[node] = value[l] <= value[r] ? l : r;
    }
  }
} function tournamentSort(arr) {
  const n = arr.length;
  let size = 1;
  while (size < n) size <<= 1;                 // leaves = power of two
  const value = Array.from({ length: size }, (_, i) => i < n ? arr[i] : Infinity);
  const win = new Array(2 * size).fill(-1);    // win[node] = leaf index of subtree min
  for (let i = 0; i < size; i++) win[size + i] = i;
  // Build the bracket bottom-up: each parent holds its smaller child.
  for (let node = size - 1; node >= 1; node--) {
    const l = win[2 * node], r = win[2 * node + 1];
    win[node] = value[l] <= value[r] ? l : r;
  }
  for (let out = 0; out < n; out++) {
    const champ = win[1];                       // champion = current minimum
    arr[out] = value[champ];
    value[champ] = Infinity;                    // retire that leaf
    // Replay only the path from the retired leaf to the root: O(log n).
    for (let node = (size + champ) >> 1; node >= 1; node >>= 1) {
      const l = win[2 * node], r = win[2 * node + 1];
      win[node] = value[l] <= value[r] ? l : r;
    }
  }
} function tournamentSort(arr) {
  const n = arr.length;
  let size = 1;
  while (size < n) size <<= 1;                 // leaves = power of two
  const value = Array.from({ length: size }, (_, i) => i < n ? arr[i] : Infinity);
  const win = new Array(2 * size).fill(-1);    // win[node] = leaf index of subtree min
  for (let i = 0; i < size; i++) win[size + i] = i;
  // Build the bracket bottom-up: each parent holds its smaller child.
  for (let node = size - 1; node >= 1; node--) {
    const l = win[2 * node], r = win[2 * node + 1];
    win[node] = value[l] <= value[r] ? l : r;
  }
  for (let out = 0; out < n; out++) {
    const champ = win[1];                       // champion = current minimum
    arr[out] = value[champ];
    value[champ] = Infinity;                    // retire that leaf
    // Replay only the path from the retired leaf to the root: O(log n).
    for (let node = (size + champ) >> 1; node >= 1; node >>= 1) {
      const l = win[2 * node], r = win[2 * node + 1];
      win[node] = value[l] <= value[r] ? l : r;
    }
  }
} function tournamentSort(arr) {
  const n = arr.length;
  let size = 1;
  while (size < n) size <<= 1;                 // leaves = power of two
  const value = Array.from({ length: size }, (_, i) => i < n ? arr[i] : Infinity);
  const win = new Array(2 * size).fill(-1);    // win[node] = leaf index of subtree min
  for (let i = 0; i < size; i++) win[size + i] = i;
  // Build the bracket bottom-up: each parent holds its smaller child.
  for (let node = size - 1; node >= 1; node--) {
    const l = win[2 * node], r = win[2 * node + 1];
    win[node] = value[l] <= value[r] ? l : r;
  }
  for (let out = 0; out < n; out++) {
    const champ = win[1];                       // champion = current minimum
    arr[out] = value[champ];
    value[champ] = Infinity;                    // retire that leaf
    // Replay only the path from the retired leaf to the root: O(log n).
    for (let node = (size + champ) >> 1; node >= 1; node >>= 1) {
      const l = win[2 * node], r = win[2 * node + 1];
      win[node] = value[l] <= value[r] ? l : r;
    }
  }
} function tournamentSort(arr) {
  const n = arr.length;
  let size = 1;
  while (size < n) size <<= 1;                 // leaves = power of two
  const value = Array.from({ length: size }, (_, i) => i < n ? arr[i] : Infinity);
  const win = new Array(2 * size).fill(-1);    // win[node] = leaf index of subtree min
  for (let i = 0; i < size; i++) win[size + i] = i;
  // Build the bracket bottom-up: each parent holds its smaller child.
  for (let node = size - 1; node >= 1; node--) {
    const l = win[2 * node], r = win[2 * node + 1];
    win[node] = value[l] <= value[r] ? l : r;
  }
  for (let out = 0; out < n; out++) {
    const champ = win[1];                       // champion = current minimum
    arr[out] = value[champ];
    value[champ] = Infinity;                    // retire that leaf
    // Replay only the path from the retired leaf to the root: O(log n).
    for (let node = (size + champ) >> 1; node >= 1; node >>= 1) {
      const l = win[2 * node], r = win[2 * node + 1];
      win[node] = value[l] <= value[r] ? l : r;
    }
  }
} 