Tournament sort
Sorting algorithm
- 7 min read
- 3 chapters
Related on Lably
Through Big O notation and Scheme (programming language)
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.
Sign in to keep reading
2 more chapters are free with a Lably account.
Etymology
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 a 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.
Implementations
Haskell
The following is an implementation of tournament sort in Haskell, based on Scheme code by Stepanov and Kershenbaum.
<span id="mwKQ"></span><span class="kr" id="mwKg">import</span><span class="w" id="mwKw"> </span><span class="nn" id="mwLA">Data.Tree</span> <span class="c1" id="mwLQ">-- | Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report.</span> <span class="nf" id="mwLg">tournamentSort</span><span class="w" id="mwLw"> </span><span class="ow" id="mwMA">::</span><span class="w" id="mwMQ"> </span><span class="kt" id="mwMg">Ord</span><span class="w" id="mwMw"> </span><span class="n" id="mwNA">t</span> <span class="w" id="mwNQ"> </span><span class="ow" id="mwNg">=></span><span class="w" id="mwNw"> </span><span class="p" id="mwOA">[</span><span class="n" id="mwOQ">t</span><span class="p" id="mwOg">]</span><span class="w" id="mwOw"> </span><span class="c1" id="mwPA">-- ^ Input: an unsorted list</span> <span class="w" id="mwPQ"> </span><span class="ow" id="mwPg">-></span><span class="w" id="mwPw"> </span><span class="p" id="mwQA">[</span><span class="n" id="mwQQ">t</span><span class="p" id="mwQg">]</span><span class="w" id="mwQw"> </span><span class="c1" id="mwRA">-- ^ Result: sorted version of the input</span> <span class="nf" id="mwRQ">tournamentSort</span><span class="w" id="mwRg"> </span><span class="n" id="mwRw">alist</span> <span class="w" id="mwSA"> </span><span class="ow" id="mwSQ">=</span><span class="w" id="mwSg"> </span><span class="n" id="mwSw">go</span><span class="w" id="mwTA"> </span><span class="p" id="mwTQ">(</span><span class="n" id="mwTg">pure</span><span class="o" id="mwTw"><$></span><span class="n" id="mwUA">alist</span><span class="p" id="mwUQ">)</span><span class="w" id="mwUg"> </span><span class="c1" id="mwUw">-- first, wrap each element as a single-tree forest</span> <span class="w" id="mwVA"> </span><span class="kr" id="mwVQ">where</span><span class="w" id="mwVg"> </span><span class="n" id="mwVw">go</span><span class="w" id="mwWA"> </span><span class="kt" id="mwWQ">[]</span><span class="w" id="mwWg"> </span><span class="ow" id="mwWw">=</span><span class="w" id="mwXA"> </span><span class="kt" id="mwXQ">[]</span> <span class="w" id="mwXg"> </span><span class="n" id="mwXw">go</span><span class="w" id="mwYA"> </span><span class="n" id="mwYQ">trees</span><span class="w" id="mwYg"> </span><span class="ow" id="mwYw">=</span><span class="w" id="mwZA"> </span><span class="p" id="mwZQ">(</span><span class="n" id="mwZg">rootLabel</span><span class="w" id="mwZw"> </span><span class="n" id="mwaA">winner</span><span class="p" id="mwaQ">)</span><span class="w" id="mwag"> </span><span class="kt" id="mwaw">:</span><span class="w" id="mwbA"> </span><span class="p" id="mwbQ">(</span><span class="n" id="mwbg">go</span><span class="w" id="mwbw"> </span><span class="p" id="mwcA">(</span><span class="n" id="mwcQ">subForest</span><span class="w" id="mwcg"> </span><span class="n" id="mwcw">winner</span><span class="p" id="mwdA">))</span> <span class="w" id="mwdQ"> </span><span class="kr" id="mwdg">where</span><span class="w" id="mwdw"> </span><span class="n" id="mweA">winner</span><span class="w" id="mweQ"> </span><span class="ow" id="mweg">=</span><span class="w" id="mwew"> </span><span class="n" id="mwfA">playTournament</span><span class="w" id="mwfQ"> </span><span class="n" id="mwfg">trees</span> <span class="c1" id="mwfw">-- | Adapted from `TOURNAMENT!` in the Stepanov and Kershenbaum report</span> <span class="nf" id="mwgA">playTournament</span><span class="w" id="mwgQ"> </span><span class="ow" id="mwgg">::</span><span class="w" id="mwgw"> </span><span class="kt" id="mwhA">Ord</span><span class="w" id="mwhQ"> </span><span class="n" id="mwhg">t</span> <span class="w" id="mwhw"> </span><span class="ow" id="mwiA">=></span><span class="w" id="mwiQ"> </span><span class="kt" id="mwig">Forest</span><span class="w" id="mwiw"> </span><span class="n" id="mwjA">t</span><span class="w" id="mwjQ"> </span><span class="c1" id="mwjg">-- ^ Input forest</span> <span class="w" id="mwjw"> </span><span class="ow" id="mwkA">-></span><span class="w" id="mwkQ"> </span><span class="kt" id="mwkg">Tree</span><span class="w" id="mwkw"> </span><span class="n" id="mwlA">t</span><span class="w" id="mwlQ"> </span><span class="c1" id="mwlg">-- ^ The last promoted tree in the input</span> <span class="nf" id="mwlw">playTournament</span><span class="w" id="mwmA"> </span><span class="p" id="mwmQ">[</span><span class="n" id="mwmg">tree</span><span class="p" id="mwmw">]</span><span class="w" id="mwnA"> </span><span class="ow" id="mwnQ">=</span><span class="w" id="mwng"> </span><span class="n" id="mwnw">tree</span> <span class="nf" id="mwoA">playTournament</span><span class="w" id="mwoQ"> </span><span class="n" id="mwog">trees</span><span class="w" id="mwow"> </span><span class="ow" id="mwpA">=</span><span class="w" id="mwpQ"> </span><span class="n" id="mwpg">playTournament</span><span class="w" id="mwpw"> </span><span class="p" id="mwqA">(</span><span class="n" id="mwqQ">playRound</span><span class="w" id="mwqg"> </span><span class="n" id="mwqw">trees</span><span class="w" id="mwrA"> </span><span class="kt" id="mwrQ">[]</span><span class="p" id="mwrg">)</span> <span class="c1" id="mwrw">-- | Adapted from `TOURNAMENT-ROUND!` in the Stepanov and Kershenbaum report</span> <span class="nf" id="mwsA">playRound</span><span class="w" id="mwsQ"> </span><span class="ow" id="mwsg">::</span><span class="w" id="mwsw"> </span><span class="kt" id="mwtA">Ord</span><span class="w" id="mwtQ"> </span><span class="n" id="mwtg">t</span> <span class="w" id="mwtw"> </span><span class="ow" id="mwuA">=></span><span class="w" id="mwuQ"> </span><span class="kt" id="mwug">Forest</span><span class="w" id="mwuw"> </span><span class="n" id="mwvA">t</span><span class="w" id="mwvQ"> </span><span class="c1" id="mwvg">-- ^ A forest of trees that have not yet competed in round</span> <span class="w" id="mwvw"> </span><span class="ow" id="mwwA">-></span><span class="w" id="mwwQ"> </span><span class="kt" id="mwwg">Forest</span><span class="w" id="mwww"> </span><span class="n" id="mwxA">t</span><span class="w" id="mwxQ"> </span><span class="c1" id="mwxg">-- ^ A forest of trees that have won in round</span> <span class="w" id="mwxw"> </span><span class="ow" id="mwyA">-></span><span class="w" id="mwyQ"> </span><span class="kt" id="mwyg">Forest</span><span class="w" id="mwyw"> </span><span class="n" id="mwzA">t</span><span class="w" id="mwzQ"> </span><span class="c1" id="mwzg">-- ^ Output: a forest containing promoted versions</span> <span class="w" id="mwzw"> </span><span class="c1" id="mw0A">-- of the trees that won their games</span> <span class="nf" id="mw0Q">playRound</span><span class="w" id="mw0g"> </span><span class="kt" id="mw0w">[]</span><span class="w" id="mw1A"> </span><span class="n" id="mw1Q">done</span><span class="w" id="mw1g"> </span><span class="ow" id="mw1w">=</span><span class="w" id="mw2A"> </span><span class="n" id="mw2Q">done</span> <span class="nf" id="mw2g">playRound</span><span class="w" id="mw2w"> </span><span class="p" id="mw3A">[</span><span class="n" id="mw3Q">tree</span><span class="p" id="mw3g">]</span><span class="w" id="mw3w"> </span><span class="n" id="mw4A">done</span><span class="w" id="mw4Q"> </span><span class="ow" id="mw4g">=</span><span class="w" id="mw4w"> </span><span class="n" id="mw5A">tree</span><span class="kt" id="mw5Q">:</span><span class="n" id="mw5g">done</span> <span class="nf" id="mw5w">playRound</span><span class="w" id="mw6A"> </span><span class="p" id="mw6Q">(</span><span class="n" id="mw6g">tree0</span><span class="kt" id="mw6w">:</span><span class="n" id="mw7A">tree1</span><span class="kt" id="mw7Q">:</span><span class="n" id="mw7g">trees</span><span class="p" id="mw7w">)</span><span class="w" id="mw8A"> </span><span class="n" id="mw8Q">done</span><span class="w" id="mw8g"> </span><span class="ow" id="mw8w">=</span><span class="w" id="mw9A"> </span><span class="n" id="mw9Q">playRound</span><span class="w" id="mw9g"> </span><span class="n" id="mw9w">trees</span><span class="w" id="mw-A"> </span><span class="p" id="mw-Q">(</span><span class="n" id="mw-g">winner</span><span class="kt" id="mw-w">:</span><span class="n" id="mw_A">done</span><span class="p" id="mw_Q">)</span> <span class="w" id="mw_g"> </span><span class="kr" id="mw_w">where</span><span class="w" id="mwAQA"> </span><span class="n" id="mwAQE">winner</span><span class="w" id="mwAQI"> </span><span class="ow" id="mwAQM">=</span><span class="w" id="mwAQQ"> </span><span class="n" id="mwAQU">playGame</span><span class="w" id="mwAQY"> </span><span class="n" id="mwAQc">tree0</span><span class="w" id="mwAQg"> </span><span class="n" id="mwAQk">tree1</span> <span class="c1" id="mwAQo">-- | Adapted from `TOURNAMENT-PLAY!` in the Stepanov and Kershenbaum report</span> <span class="nf" id="mwAQs">playGame</span><span class="w" id="mwAQw"> </span><span class="ow" id="mwAQ0">::</span><span class="w" id="mwAQ4"> </span><span class="kt" id="mwAQ8">Ord</span><span class="w" id="mwARA"> </span><span class="n" id="mwARE">t</span> <span class="w" id="mwARI"> </span><span class="ow" id="mwARM">=></span><span class="w" id="mwARQ"> </span><span class="kt" id="mwARU">Tree</span><span class="w" id="mwARY"> </span><span class="n" id="mwARc">t</span><span class="w" id="mwARg"> </span><span class="c1" id="mwARk">-- ^ Input: ...</span> <span class="w" id="mwARo"> </span><span class="ow" id="mwARs">-></span><span class="w" id="mwARw"> </span><span class="kt" id="mwAR0">Tree</span><span class="w" id="mwAR4"> </span><span class="n" id="mwAR8">t</span><span class="w" id="mwASA"> </span><span class="c1" id="mwASE">-- ^ ... two trees</span> <span class="w" id="mwASI"> </span><span class="ow" id="mwASM">-></span><span class="w" id="mwASQ"> </span><span class="kt" id="mwASU">Tree</span><span class="w" id="mwASY"> </span><span class="n" id="mwASc">t</span><span class="w" id="mwASg"> </span><span class="c1" id="mwASk">-- ^ Result: `promote winner loser`, where `winner` is</span> <span class="w" id="mwASo"> </span><span class="c1" id="mwASs">-- the tree with the *lesser* root of the two inputs</span> <span class="nf" id="mwASw">playGame</span><span class="w" id="mwAS0"> </span><span class="n" id="mwAS4">tree1</span><span class="w" id="mwAS8"> </span><span class="n" id="mwATA">tree2</span> <span class="w" id="mwATE"> </span><span class="o" id="mwATI">|</span><span class="w" id="mwATM"> </span><span class="n" id="mwATQ">rootLabel</span><span class="w" id="mwATU"> </span><span class="n" id="mwATY">tree1</span><span class="w" id="mwATc"> </span><span class="o" id="mwATg"><=</span><span class="w" id="mwATk"> </span><span class="n" id="mwATo">rootLabel</span><span class="w" id="mwATs"> </span><span class="n" id="mwATw">tree2</span><span class="w" id="mwAT0"> </span><span class="ow" id="mwAT4">=</span><span class="w" id="mwAT8"> </span><span class="n" id="mwAUA">promote</span><span class="w" id="mwAUE"> </span><span class="n" id="mwAUI">tree1</span><span class="w" id="mwAUM"> </span><span class="n" id="mwAUQ">tree2</span> <span class="w" id="mwAUU"> </span><span class="o" id="mwAUY">|</span><span class="w" id="mwAUc"> </span><span class="n" id="mwAUg">otherwise</span><span class="w" id="mwAUk"> </span><span class="ow" id="mwAUo">=</span><span class="w" id="mwAUs"> </span><span class="n" id="mwAUw">promote</span><span class="w" id="mwAU0"> </span><span class="n" id="mwAU4">tree2</span><span class="w" id="mwAU8"> </span><span class="n" id="mwAVA">tree1</span> <span class="c1" id="mwAVE">-- | Adapted from `GRAB!` in the Stepanov and Kershenbaum report</span> <span class="nf" id="mwAVI">promote</span><span class="w" id="mwAVM"> </span><span class="ow" id="mwAVQ">::</span><span class="w" id="mwAVU"> </span><span class="kt" id="mwAVY">Tree</span><span class="w" id="mwAVc"> </span><span class="n" id="mwAVg">t</span><span class="w" id="mwAVk"> </span><span class="c1" id="mwAVo">-- ^ The `winner`</span> <span class="w" id="mwAVs"> </span><span class="ow" id="mwAVw">-></span><span class="w" id="mwAV0"> </span><span class="kt" id="mwAV4">Tree</span><span class="w" id="mwAV8"> </span><span class="n" id="mwAWA">t</span><span class="w" id="mwAWE"> </span><span class="c1" id="mwAWI">-- ^ The `loser`</span> <span class="w" id="mwAWM"> </span><span class="ow" id="mwAWQ">-></span><span class="w" id="mwAWU"> </span><span class="kt" id="mwAWY">Tree</span><span class="w" id="mwAWc"> </span><span class="n" id="mwAWg">t</span><span class="w" id="mwAWk"> </span><span class="c1" id="mwAWo">-- ^ Result: a tree whose root is the root of `winner`</span> <span class="w" id="mwAWs"> </span><span class="c1" id="mwAWw">-- and whose children are:</span> <span class="w" id="mwAW0"> </span><span class="c1" id="mwAW4">-- * `loser`,</span> <span class="w" id="mwAW8"> </span><span class="c1" id="mwAXA">-- * all the children of `winner`</span> <span class="nf" id="mwAXE">promote</span><span class="w" id="mwAXI"> </span><span class="n" id="mwAXM">winner</span><span class="w" id="mwAXQ"> </span><span class="n" id="mwAXU">loser</span><span class="w" id="mwAXY"> </span><span class="ow" id="mwAXc">=</span><span class="w" id="mwAXg"> </span><span class="kt" id="mwAXk">Node</span><span class="w" id="mwAXo"> </span><span class="p" id="mwAXs">{</span> <span class="w" id="mwAXw"> </span><span class="n" id="mwAX0">rootLabel</span><span class="w" id="mwAX4"> </span><span class="ow" id="mwAX8">=</span><span class="w" id="mwAYA"> </span><span class="n" id="mwAYE">rootLabel</span><span class="w" id="mwAYI"> </span><span class="n" id="mwAYM">winner</span><span class="p" id="mwAYQ">,</span> <span class="w" id="mwAYU"> </span><span class="n" id="mwAYY">subForest</span><span class="w" id="mwAYc"> </span><span class="ow" id="mwAYg">=</span><span class="w" id="mwAYk"> </span><span class="n" id="mwAYo">loser</span><span class="w" id="mwAYs"> </span><span class="kt" id="mwAYw">:</span><span class="w" id="mwAY0"> </span><span class="n" id="mwAY4">subForest</span><span class="w" id="mwAY8"> </span><span class="n" id="mwAZA">winner</span><span class="p" id="mwAZE">}</span> <span class="nf" id="mwAZI">main</span><span class="w" id="mwAZM"> </span><span class="ow" id="mwAZQ">::</span><span class="w" id="mwAZU"> </span><span class="kt" id="mwAZY">IO</span><span class="w" id="mwAZc"> </span><span class="nb" id="mwAZg">()</span> <span class="nf" id="mwAZk">main</span><span class="w" id="mwAZo"> </span><span class="ow" id="mwAZs">=</span><span class="w" id="mwAZw"> </span><span class="n" id="mwAZ0">print</span><span class="w" id="mwAZ4"> </span><span class="o" id="mwAZ8">$</span><span class="w" id="mwAaA"> </span><span class="n" id="mwAaE">tournamentSort</span><span class="w" id="mwAaI"> </span><span class="n" id="mwAaM">testList</span> <span class="w" id="mwAaQ"> </span><span class="kr" id="mwAaU">where</span><span class="w" id="mwAaY"> </span><span class="n" id="mwAac">testList</span><span class="w" id="mwAag"> </span><span class="ow" id="mwAak">=</span><span class="w" id="mwAao"> </span><span class="p" id="mwAas">[</span><span class="mi" id="mwAaw">0</span><span class="p" id="mwAa0">,</span><span class="w" id="mwAa4"> </span><span class="mi" id="mwAa8">1</span><span class="p" id="mwAbA">,</span><span class="w" id="mwAbE"> </span><span class="mi" id="mwAbI">2</span><span class="p" id="mwAbM">,</span><span class="w" id="mwAbQ"> </span><span class="mi" id="mwAbU">3</span><span class="p" id="mwAbY">,</span><span class="w" id="mwAbc"> </span><span class="mi" id="mwAbg">4</span><span class="p" id="mwAbk">,</span><span class="w" id="mwAbo"> </span><span class="mi" id="mwAbs">5</span><span class="p" id="mwAbw">]</span>