Tournament Sort
This page gives a brief introduction to tournament sort.
Definition
Tournament sort, also known as tree selection sort, is an improved version of selection sort and a variant of heapsort (both use a complete binary tree). It is selection sort that uses a priority queue to find the next element to select.
Introduction
Tournament sort is named after the single-elimination tournament. In this contest format many contestants take part; they are compared in pairs, and the winner of each pair advances to the next round. Elimination of this kind determines the best contestant, but the contestant knocked out in the final round is not necessarily the second best: he may be worse than a contestant knocked out earlier.
Procedure
Take a min tournament tree as the example:
The leaves show the elements to be sorted. The red edges show the path along which the smaller element of each round of comparisons advances. Clearly, one tournament selects the smallest element of a set.
A round of comparisons among \(n\) elements produces \(\left\lceil\dfrac{n}{2}\right\rceil\) winners: the smaller element of each pair goes on to the next round. An element that cannot be paired up goes straight to the next round.
After a tournament, the selected element has to be removed. Simply set it to \(\infty\) (much as in heapsort) and hold another tournament to select the second smallest element.
Repeat this until all elements are sorted.
Properties
Stability
Tournament sort is an unstable sorting algorithm.
Time complexity
The best-case, average-case and worst-case time complexity of tournament sort are all \(O(n\log n)\). It takes \(O(n)\) time to set up the tournament and then \(O(\log n)\) time to select one element out of the \(n\) elements.
Space complexity
Tournament sort uses \(O(n)\) space.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | |
External links
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: ShaoChenHeng, 24OI-bot, NachtgeistW, Xeonacid, zhoudavinci, Enter-tainer, iamtwz, mcendu, Alisahhh, ksyx, Ir1d, Menci, shawlleyw, shenshuaijie, Tiphereth-A, Chihsiao, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.