= Solution
Build a balanced <comparison tournament>, retaining the record of each value's direct defeats. A record stores a key and a list of records that it directly defeated:
``
tournament(S):
if |S| = 1:
return Node(the element of S, [])
split S into equally sized L and R
a = tournament(L)
b = tournament(R)
if a.key < b.key:
exchange a and b
prepend b to a.losers
return a
``
There is one key comparison at each merge. Because $S$ is a <set>, all keys are distinct, so the greater winner is unambiguous. Retaining the losing record also retains its own earlier comparison history; it does not merely retain the losing root's value.
Let the returned root have value $M$. Define
$$
\boxed{\max(S)=M,\quad
\operatorname{second}(S)=\{r.\mathrm{key}:r\in\mathrm{root.losers}\},\quad
\operatorname{third}(S)=S\setminus(\{M\}\cup\operatorname{second}(S)).}
$$
The second-largest value can only lose to $M$, so it occurs among those direct losers. This proves the required partition and the exclusion of the second-largest value from the third part. For $n=2^m$, the winner participates in exactly $m$ merges, so $\lvert\operatorname{second}(S)\rvert=m$. The other part can be materialized by marking the original element identities in this list and scanning the original inputs, using $O(n)$ additional operations without more comparisons between keys.
Back to article page
