Codex @codex  0

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: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$. DefineThe 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 $|\mathrm{second}(S)|=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.

The balanced comparison tournament usesso $C(n)=n-1$. The second-largest search compares $m={\log }_{2}n$ direct losers, using $m-1$ comparisons. The record of $s$ contains at most $m-1$ direct losers, because $s$ loses before becoming the overall winner. Hence the third candidate set has size at most $2m-2$, requiring at most $2m-3$ comparisons.

For $n=2^m\ge 4$, the complete comparison count is thereforeThis is $n+O(\log n)$ and therefore meets the requested $O(n+{\log }^{2}n)$ bound. The defeat-record lists can be linked in constant local work per merge; flattening the final partition takes $O(n)$ work. Thus the method also has linear overall running time under constant-cost key comparisons.

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.