= Tournament selection of the three largest elements
{title2=$n+3\log_2n-5\text{ key comparisons suffice for }n=2^m\geq4$}
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.
Back to article page
