= Comparison tournament
{title2=$n-1\text{ comparisons to find the maximum}$}
Pair candidates from a <totally ordered set> and retain the greater one from each comparison until one winner remains. Every other candidate loses once, so $n-1$ key comparisons suffice to find the <maximum> of $n$ distinct values. A balanced tournament on $2^m$ inputs gives the winner $m$ direct losers. Retaining each loser's own defeat record preserves information for finding later order statistics. The comparison records form a rooted tree and are distinct from a graph-theoretic <tournament>, which includes a directed comparison between every pair.
Back to article page
