Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 5 / b / 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: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.