Finding the Salutatorian

One other cute trick, before we look at a more general and useful algorithm.

How many comparisons does it take to find the second largest element in a list?

Easy to solve using 2n-3 comparisons by pulling out the largest, then taking the max of the remaining n-1 elements.

Can solve this in $n + \log n - 2$ comparisons. (It only took 5 times longer in my experiments.)