Tournament sort

Tournament sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n log n)
Average performance	O(n log n)

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 O(n) operations to select the next element of n elements; in a tournament sort, it takes O(log n) operations (after building the initial tournament in O(n)). Tournament sort is a variation of heapsort.

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.^[1]

Tournament sorts may also be used in N-way merges.

The tournament

The name comes from its similarity to a single-elimination tournament 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.

Implementation

The following is an implementation of tournament sort in Haskell, based on Scheme code by Stepanov and Kershenbaum.^[2]

import Data.Tree

nodify :: [t0] -> [Tree t0]
{-  Adapted from `LISTIFY!` in the Stepanov and Kershenbaum report
    Input:
        `alist`; a list of items to be sorted
    Output:
        a forest of trivial trees, such that each tree has one element of `alist` as its `rootLabel` -}
nodify alist = map ( \u -> Node {rootLabel=u, subForest=[]} ) alist

promote :: Tree t0 -> Tree t0 -> Tree t0
{-  Adapted from `GRAB!` in the Stepanov and Kershenbaum report
    Input:
        `loser`, `winner`; trees
    Output:
        a tree whose root is the root of `winner` and whose children are:
            * `loser`,
            * and all the children of `winner` -}
promote winner loser = Node {
    rootLabel = rootLabel winner,
    subForest = loser : subForest winner}

playGame :: (t0 -> t0 -> Bool) -> Tree t0 -> Tree t0 -> Tree t0
{-  Adapted from `TOURNAMENT-PLAY!` in the Stepanov and Kershenbaum report
    Input:
       `inc`; a two-argument predicate that returns `True` if its arguments are in increasing order
       `tree1`, `tree2`; trees whose roots will be referred to as `r1` and `r2`
    Output:
        `promote winner loser` where `winner` is the tree among `tree1` and `tree2` with the *lesser* root-}
playGame inc tree1 tree2
    | i == True  = promote tree1 tree2
    | otherwise  = promote tree2 tree1
    where
        r1 = rootLabel tree1
        r2 = rootLabel tree2
        i = inc r1 r2

playRound :: (t0 -> t0 -> Bool) -> Forest t0 -> Forest t0 -> Forest t0
{-  Adapted from `TOURNAMENT-ROUND!` in the Stepanov and Kershenbaum report
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `to_do`; a forest of trees that have not yet competed in round
        `done`; a forest of trees that have won in round
    Output:
        `winners`; a forest containing promoted versions of the trees that won their games -}
playRound inc [] done = done
playRound inc [tree] done = tree:done
playRound inc (tree1:tree2:trees) done = playRound inc trees (winner:done)
    where winner = playGame inc tree1 tree2

playTournament :: (t0 -> t0 -> Bool) -> Forest t0 -> Tree t0
{-  Adapted from `TOURNAMENT!` in the Stepanov and Kershenbaum report
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `trees`; a forest of trees
    Output:
        `winner`; the last promoted tree -}
playTournament inc [tree] = tree
playTournament inc trees = playTournament inc (playRound inc trees [])

tournamentSortSimple :: (t0 -> t0 -> Bool) -> Forest t0 -> [t0]
{-  Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report, but not the final function because it still takes a forest, not a list of elements, as input.
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `trees`; a forest of trees
    Output:
        `sortedTrees`; `trees`, but in increasing order by root
-}
tournamentSortSimple inc [] = []
tournamentSortSimple inc trees = r : tournamentSortSimple inc sf
    where
        len = length trees
        winner = playTournament inc trees
        r = rootLabel winner
        sf = subForest winner

tournamentSort :: (t0 -> t0 -> Bool) -> [t0] -> [t0]
{-  The complete sort.
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `alist`; an unsorted list
    Output:
        sorted version of `alist`
-}
tournamentSort inc alist = tournamentSortSimple inc (nodify alist)

inc1 :: Ord t0 => t0 -> t0 -> Bool
-- The two-argument predicate mentioned repeatedly until this point. Perhaps we could have simply used `<` without requiring an additional argument, but it's nice to be able to write a predicate to compare whatever we want without necessarily defining an entire order structure.
inc1 a b = a < b

testList = [-0.202669, 0.969870, 0.142410, -0.685051, 0.487489, -0.339971, 0.832568, 0.00510796, -0.822352, 0.350187, -0.477273, 0.695266]
sortedList = tournamentSort inc1 testList

main = print sortedList

References

1. Donald Knuth, The Art of Computer Programming, Sorting and Searching, Volume 3, 1973. The "snowplow" argument. p. 254
2. Stepanov, Alexander and Aaron Kershenbaum. Using Tournament Trees to Sort, Brooklyn: Center for Advanced Technology in Telecommunications, 1986.