How fast can a sorting algorithm be?¶

Here is a brief and informal argument that a sorting algorithm that relies only on comparisons of individual elements (note: this excludes Bucket Sort, which relies on the elements of the list being of a certain type and in a certain range), cannot run faster than $\mathcal{O}(n\log n)$.

There are $n!$ ways to rearrange a list of length $n$. One of them leads to the list being sorted (if all the elements in the list are unique.)

Now, each time we ask a question like "is element i smaller than element j?," the best we can hope for is to eliminate one half of the possibile rearrangements. If all we're allowed to do is compare elements, we'd keep asking questions like this until we get to the point that only one rearrangement is left. This is similar to how in the game of Twenty Questions, we ask yes/no questions and eliminate possible answers.

So, we start out with $n!$ possible rearrangements, after the first comparison there will be $n!/2$ possible rearrangements, and so on, until we just have the one rearrangement which leads to the list being sorted.

In total, we need $\log_2 (n!)$ comparisons if each comparison eliminates half the remaining rearrangements.

Now, we need to use Stirling's Approximation:

$$n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n,$$

where $e \approx 2.71$ is Euler's Constant.

Using Striling's approximation, we get that $\log_2(n!)$ is $\mathcal{O}(n\log(n))$.