Algorithm to find the second smallest element I am having trouble with the following homework assignment:
Give an algorithm that finds the second smallest of n elements in at most
$n + \lceil\log(n)\rceil - 2$ comparisons.
I have been trying to find an algorithm myself, and believe I have to check the elements in pairs and then recurse on the smallest elements. However, when I tried an algorithm like this the amount of comparisons it took where $n + \lceil\log(n)\rceil$ (according to me).
This is the algorithm in question:
1. secondSmallest(A[n])
2.    if A.length >= 2 then
3.       for i = 1 to i = A.length do
4.          if A[i] < A[i + 1] then
5.             B[(i+1)/2] = A[i]
6.             i + +
7.          else
8.             B[(i+1)/2] = A[i + 1]
9.            i + +
10.         endif
11.      return secondSmallest(B[n])
12.    else
13.       if A[1] < A[2] then
14.          return A[2]
16.       else return A[1]
17.       endif
18.    endif

Note: this is pseudocode, and by no means accurate. And the logarithm is a BASE 2 logarithm.
 A: SKETCH: Assuming that you’re allowed to use extra storage, run the comparison as a single elimination tournament, keeping a record of the entries beaten by each winner along the way. (Low number wins.) When you get an overall winner, you have only to identify the winner among the $\lceil \lg n\rceil$ contestants beaten by the overall winner.
Added: On further thought, I see that one doesn’t actually need additional memory, if one rearranges the list. Implement the single elimination tournament as follows.
Suppose that the numbers are $a_0,a_1,\dots,a_{n-1}$. On the first pass compare $a_{2k}$ with $a_{2k+1}$ for $0\le k<(n-1)/2$; if $a_{2k}>a_{2k+1}$, interchange them. On the second pass compare $a_{4k}$ with $a_{4k+2}$ for $0\le k<(n-2)/4$; if $a_{4k}>a_{4k+2}$, interchange the pair $\langle a_{4k},a_{4k+1}\rangle$ with the pair $\langle a_{4k+2},a_{4k+3}\rangle$. On the $i$-th pass compare $a_{2^ik}$ with $a_{2^ik+2^{i-1}}$ for $0\le i<(n-2^{i-1})/2^i$; if $a_{2^ik}>a_{2^ik+2^{i-1}}$, interchange the blocks of length $2^{i-1}$ beginning at $a_{2^ik}$ and $a_{2^ik+2^{i-1}}$. This continues as long as $n-2^{i-1}>0$, i.e., until $n\le 2^{i-1}$; thus, if the last pass is the $m$-th pass, then $2^{m-1}<n\le 2^m$, or $\lceil\lg n\rceil=m$. The smallest number in the set is now $a_0$, and every other number in the set has lost exactly one comparison, so we’ve made $n-1$ comparisons.
The numbers that are now $a_{2^i}$ for $i=0,\dots,m-1$ are the numbers that lost to $a_0$ in direct comparisons; every number in the set that is neither $a_0$ nor one of these $m$ numbers lost a direct comparison to one of these $m$ numbers and therefore cannot be the second-smallest number in the set. Thus, the second-smallest number is the smallest of the $a_{2^i}$ for $i=0,\dots,m-1$. There are $m$ of these numbers, so it takes $m-1$ comparisons to find the smallest.
Altogether, then, this algorithm takes $$(n-1)+(m-1)=n-1+\lceil\lg n\rceil-1=n+\lceil\lg n\rceil-2$$ comparisons, as required.
A: Consider the following list of numbers: $3, 4, 5, 2, 1, 7, 8, 9$.
While passing through the first stage of Brian M. Scott's algorithm above, after each pass the list changes as follows:
$$
\begin{array}{l|cccccccc}
              & a_0 & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 \\
\hline
\text{start}  & 3 & 4 & 5 & 2 & 1 & 7 & 8 & 9 \\
\text{pass 1} & 3 & 4 & 2 & 5 & 1 & \color{blue}{7} & 8 & 9 \\
\text{pass 2} & 2 & 4 & 3 & 5 & 1 & \color{blue}{7} & \color{blue}{8} & 9 \\
\text{pass 3} & 1 & 4 & 3 & 5 & \color{blue}{2} & \color{blue}{7} & \color{blue}{8} & 9
\end{array}
$$
(The numbers in blue are those that have been compared to the final $a_0$ (that is, $1$) up to (and including) that pass through the algorithm.)
Brian M. Scott then states

The numbers that are now $a_{2^i}$ for $i=0,\ldots,m−1$ are the numbers that lost to $a_0$ in direct comparisons;...

However neither $4$ nor $3$ were ever compared directly to $1$, and the indicies of $7$ and $8$ are not of that form.
Have I missed something?
