How do you get an algorithm for the second smallest value that for the worst case completes in: n + ceiling( lg n ) - 2 ?
The best algorithm I could get was 2n - 3 in the worst case, and it's too slow.
(For anyone who is interested tt is the question 9.1-1 from the textbook Introduction to Algorithms, second edition, by T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill.)