Find the 2nd largest element in an array with minimum number of comparisons

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.

First, compare the elements, as in the tree

   |  / \ |   |/ \ / \x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.

The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

The optimality is proved via adversary argument. See https://math.stackexchange.com/questions/1601 or http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf or http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf or https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

You can find the second largest value with at most 2·(N-1) comparisons and two variables that hold the largest and second largest value:

largest := numbers[0];secondLargest := nullfor i=1 to numbers.length-1 do    number := numbers[i];    if number > largest then        secondLargest := largest;        largest := number;    else        if number > secondLargest then            secondLargest := number;        end;    end;end;

Use Bubble sort or Selection sort algorithm which sorts the array in descending order. Don't sort the array completely. Just two passes. First pass gives the largest element and second pass will give you the second largest element.

No. of comparisons for first pass: n-1

No. of comparisons for first pass: n-2

Total no. of comparison for finding second largest: 2n-3

May be you can generalize this algorithm. If you need the 3rd largest then you make 3 passes.

By above strategy you don't need any temporary variables as Bubble sort and Selection sort are in place sorting algorithms.