Lower Bound on Comparison-Based Sorting

There are $N! = 1*2*3*...*(N-1)*N$ possible permutations on a list of length $N$.

The best I can possibly do when I do a single comparison is to halve the number of possible permutations.

Ideally, if this happens every time, how many questions do I need to ask to get to a single possibility? In other words, how many times do I need to halve $N!$ in order to get to $1$?

This simply

$\log_2(N!) = \log_2(N) + \log_2(N-1) + \log_2(N-2) + ... + \log_2(1)$

In [7]:
import numpy as np
import matplotlib.pyplot as plt
x = np.arange(1, 21)
xx = np.linspace(1, 20, 1000)
plt.plot(xx, np.log2(xx), c='C2', linewidth=4)
plt.bar(x-0.5, np.log2(x), width=1, edgecolor='C1', linewidth=2)
plt.xlim([1, 20])
plt.xticks(x)
plt.title("$\log_2(x)$")
plt.xlabel("x")
Out[7]:
Text(0.5, 0, 'x')

$\int_{1}^{N} \log_2(x) dx$

Antiderivative of $\log_2(x)$ is

$x \log_2(x) - \frac{x}{\ln(2)} + c$

$\int_{1}^{N} \log_2(x) dx = \left[x \log_2(x) - \frac{x}{\ln(2)} \right]^{N}_1$

$N \log_2(N) - N/\ln(2) + 1/\ln(2)$, which is $\Omega(N \log N)$. Therefore, comparison-based sortings have a lower bound of $\Omega(N \logN)$. Interestingly, merge sort achieves this in its worst case, so we have found an algorithm that does as well as it can on all cases!