Tournament sort
Encyclopedia
Tournament sort is a sorting algorithm
. It improves upon the naive selection sort
by using a priority queue
to find the next element in the sort. In the naive selection sort, it takes
operations to select the next element of 
elements; in a tournament sort, it takes 
operations (after building the initial tournament in 
). Tournament sort is a variation of heapsort
.
Tournament sorts may also be used in N-way merges.
where there are many players (or teams) that play in two-sided matches. Each match compares the players, and the winning player is promoted to play at match at the next level up. The hierarchy continues until the final match determines the ultimate winner. The tournament determines the best player, but the player who was beaten in the final match may not be the second best—he may be inferior to other players the winner bested.
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
. It improves upon the naive selection sort
Selection sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
by using a priority queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
to find the next element in the sort. In the naive selection sort, it takes
operations to select the next element of elements; in a tournament sort, it takes operations (after building the initial tournament in ). Tournament sort is a variation of heapsortHeapsort
Heapsort is a comparison-based sorting algorithm to create a sorted array , and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O runtime...
.
Common application
Tournament replacement selection sorts are used to gather the initial runs for external sorting algorithms. Conceptually, an external file is read and its elements are pushed into the priority queue until the queue is full. Then the minimum element is pulled from the queue and written as part of the first run. The next input element is read and pushed into the queue, and the min is selected again and added to the run. There's a small trick that if the new element being pushed into the queue is less than the last element added to the run, then the element's sort value is increased so it will be part of the next run. On average, a run will be 100% longer than the capacity of the priority queue.Tournament sorts may also be used in N-way merges.
The tournament
The name comes from its similarity to a single-elimination tournamentSingle-elimination tournament
A single-elimination tournament, also called a knockout, cup or sudden death tournament, is a type of elimination tournament where the loser of each match or bracket is immediately eliminated from winning the championship or first prize in the event...
where there are many players (or teams) that play in two-sided matches. Each match compares the players, and the winning player is promoted to play at match at the next level up. The hierarchy continues until the final match determines the ultimate winner. The tournament determines the best player, but the player who was beaten in the final match may not be the second best—he may be inferior to other players the winner bested.