Comparison tournament ($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.

After a balanced comparison tournament, the second-largest element is the maximum among the winner's $m$ direct losers. The third-largest must have lost directly to the winner or to that second-largest element: no smaller element could defeat it. Excluding the known top two leaves at most $(m-1)+(m-1)$ candidates, because the second-largest won at most $m-1$ earlier comparisons. The three stages use at most $(n-1)+(m-1)+(2m-3)$ key comparisons, proving the displayed bound. Defeat records must retain their earlier subtrees; keeping only the overall winner's direct-loser values discards information used by the last stage.