(algorithm)
Definition: (no definition here, yet, but you can help.)
See also dominance tree sort, heapsort.
Note: Heapsort is sometimes called tournament sort. Consider the tree of matches in a single-elimination sports tournament, where players' abilities are a total order. The tournament tree has the heap property. When a winner is found (the least element is chosen), the winner is removed and the appropriate matches replayed.
In Using Tournament Trees to Sort, Center for Advanced Technology in Telecommunications, Polytechnic University, Brooklyn, New York, C.A.T.T Technical Report 86-13, Alexander Stepanov and Aaron Kershenbaum extend the observation that a tournament can find the winner in N comparisons and the 2nd in log N more comparisons.
An algorithm written up in 2002 also called a tournament sort.
Kenneth E. Iverson, A Programming Language, John Wiley and Sons, 1962, pages 223-226.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 30 March 2006.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
"tournament sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 30 March 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/tournamentSort.html
