This is a very interesting problem indeed.
The problem comes in multiple flavors:
- Find two largest elements in an array in 1.5n comparisons.
- Find two largest elements in an array in n+log(n)−2 comparisons.
- Prove that no algorithm for finding two largest elements in an array can do this in less than n+ log (n)−2 comparisons.
- What is the fastest algorithm for finding three largest elements?