Definition: Find the maximum of a set of n elements in ⌈log n⌉ "rounds" (passes) by "playing" (comparing) pairs of elements and advancing the winner (greater) of each pair to the next round. It takes n-1 comparisons, like linear search, but may be parallelized, extended to also find the second greatest element, etc.
See also select kth element, select and partition.
Note: The second greatest element can be found with log n - 1 additional comparisons.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 18 March 2019.
HTML page formatted Mon Mar 25 11:53:34 2019.
Cite this as:
Gopinath Srinivasan, "tournament", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 18 March 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/tournament.html