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.

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?
