Algorithm for finding two smallest numbers in an array

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.

No, it's not optimal. Do you know an efficient way of finding the smallest number in an array? Knowing the smallest number, could you adapt that method to find the second smallest?

Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$.

It is a modified Quicksort algorithm that sorts the array but stops early, leaving the beginning part correct (in this case the first two elements) and the rest of the array in whatever partly-sorted state is most convenient.

The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$:

1. Compare $a_1$ and $a_2$, $a_3$ and $a_4$, and so on. Store only the smallest of each pair in a list $b_1,\ldots,b_{n/2}$.

2. Repeat $k-1$ more times to get the minimum $a_{\min}$.

3. Let $L$ be the set of all $k$ elements which were compared to $a_{\min}$ and were larger. Find the minimum of $L$. This is the second minimal element.

This algorithm uses $n + \log_2 n - 2$ comparisons, which is the optimal number of comparisons. However, implementing the logic isn't trivial, so in practice it might be slower than the algorithm in user2566092's answer.