Interactive demo
Tournament Sort Visualization
Tournament sort lets the elements play a knockout tournament in which the smaller one always wins. The overall winner is the smallest element. After taking it out, only the matches on its way up are played again.
Watch the colored path: after a winner leaves, only the matches on its way to the top are replayed.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element in the array
- Player in the tournament
- Replayed match
- Path of the winner
- Final position
Runtime and properties
Best case
O(n log n)
Building the bracket and replaying it always cost about log n comparisons per element.
Average case
O(n log n)
n − 1 matches build the bracket, then every winner replays only the log n matches on its way.
Worst case
O(n log n)
The bracket is balanced, whatever the order of the input.
Extra memory
O(n)
The bracket needs a node for every match.
Stable
Yes
On ties the element from the left wins, which came first.
In-place
No
The bracket is built outside the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort this page | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. The bracket
Every element enters as a leaf. In each match the smaller of two elements moves up, so after n − 1 matches the smallest element stands at the top.
2. Take out the winner
The winner goes to the next position of the array. Its leaf is now empty, so every match it took part in has to be decided again.
3. Replay only one path
All other matches keep their result, so only about log n matches are replayed per element. Heapsort uses the same idea, but stores its tree inside the array.