Tournament Sort Program with Full Explanation and Code

2025-11-19 tournament sort tree-based sort knockout sorting python tournament sort c tournament sort javascript tournament sort php tournament sort csharp tournament sort comparison sorting sorting tree algorithm

Tournament Sort is a tree-based sorting method that finds the minimum element using a knockout-style tournament. This page explains how the algorithm works and provides full implementations in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Tournament Sort?

Tournament Sort is a comparison-based sorting algorithm that determines the smallest (or largest) element using a “tournament tree” structure. Just like in sports tournaments, pairs of elements compete, and the winners move upward until the final winner (minimum element) is found. After removing the winner, the tournament is replayed until all elements are sorted.

Tournament Sort is efficient for simultaneously finding the minimum and second minimum elements. It performs well when comparisons are costly but tree maintenance is cheap. However, it is not widely used in practice because it requires extra memory.

Steps to Solve

  1. Build a complete tournament tree where each leaf contains an array element.
  2. Each internal node contains the smaller of its two child values.
  3. The root of the tree represents the smallest element.
  4. Record the winner (minimum element) and remove it from the list.
  5. Rebuild or update the tournament tree excluding the removed element.
  6. Repeat until all elements are extracted in sorted order.

Key Points

  • Mimics knockout tournament structure.
  • Useful when comparison operations are expensive.
  • Worst-case time complexity: O(n log n).
  • Requires extra memory to store the tournament tree.
  • Can efficiently find minimum, second minimum, etc.
  • Not a stable sorting algorithm.

Program Code


def build_tournament(arr):
    n = len(arr)
    tree = [None] * (2 * n)
    for i in range(n):
        tree[n + i] = arr[i]

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

    return tree

def tournament_sort(arr):
    result = []
    while arr:
        tree = build_tournament(arr)
        minimum = tree[1]
        result.append(minimum)
        arr.remove(minimum)
    return result

arr = list(map(int, input("Enter numbers: ").split()))
sorted_arr = tournament_sort(arr)
print("Sorted array:", sorted_arr)
      

#include <stdio.h>
#include <limits.h>

int buildTournament(int arr[], int n, int tree[]) {
    for (int i = 0; i < n; i++)
        tree[n + i] = arr[i];

    for (int i = n - 1; i > 0; i--)
        tree[i] = (tree[2*i] < tree[2*i+1]) ? tree[2*i] : tree[2*i+1];

    return tree[1];
}

void tournamentSort(int arr[], int n) {
    int tree[2 * n];
    int sorted[n];

    for (int k = 0; k < n; k++) {
        int minVal = buildTournament(arr, n, tree);
        sorted[k] = minVal;

        for (int i = 0; i < n; i++)
            if (arr[i] == minVal) {
                arr[i] = INT_MAX;
                break;
            }
    }

    for (int i = 0; i < n; i++)
        arr[i] = sorted[i];
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    tournamentSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
      

function buildTournament(arr) {
  let n = arr.length;
  let tree = Array(2 * n);

  for (let i = 0; i < n; i++)
    tree[n + i] = arr[i];

  for (let i = n - 1; i > 0; i--)
    tree[i] = Math.min(tree[2 * i], tree[2 * i + 1]);

  return tree;
}

function tournamentSort(arr) {
  let result = [];
  while (arr.length > 0) {
    let tree = buildTournament(arr);
    let minVal = tree[1];
    result.push(minVal);

    let idx = arr.indexOf(minVal);
    arr.splice(idx, 1);
  }
  return result;
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
console.log("Sorted array:", tournamentSort(arr));
      

using System;

class Program {

    static int[] BuildTournament(int[] arr) {
        int n = arr.Length;
        int[] tree = new int[2 * n];

        for (int i = 0; i < n; i++)
            tree[n + i] = arr[i];

        for (int i = n - 1; i > 0; i--)
            tree[i] = Math.Min(tree[2 * i], tree[2 * i + 1]);

        return tree;
    }

    static int[] TournamentSort(int[] arr) {
        int n = arr.Length;
        int[] sorted = new int[n];
        int k = 0;

        while (arr.Length > 0) {
            int[] tree = BuildTournament(arr);
            int minVal = tree[1];
            sorted[k++] = minVal;

            int index = Array.IndexOf(arr, minVal);
            var temp = new int[arr.Length - 1];
            int t = 0;

            for (int i = 0; i < arr.Length; i++)
                if (i != index)
                    temp[t++] = arr[i];

            arr = temp;
        }

        return sorted;
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int[] sorted = TournamentSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in sorted)
            Console.Write(x + " ");
    }
}
      

<?php

function buildTournament($arr) {
    $n = count($arr);
    $tree = array_fill(0, 2 * $n, 0);

    for ($i = 0; $i < $n; $i++)
        $tree[$n + $i] = $arr[$i];

    for ($i = $n - 1; $i > 0; $i--)
        $tree[$i] = min($tree[2 * $i], $tree[2 * $i + 1]);

    return $tree;
}

function tournamentSort($arr) {
    $sorted = [];

    while (count($arr) > 0) {
        $tree = buildTournament($arr);
        $minVal = $tree[1];
        $sorted[] = $minVal;

        $index = array_search($minVal, $arr);
        array_splice($arr, $index, 1);
    }

    return $sorted;
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
$sorted = tournamentSort($arr);

echo "Sorted array: " . implode(" ", $sorted);

?>
1