A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements
Following the conventions of Peczarski, Towards Optimal Sorting of 16 Elements, let us denote by $S(n)$ the optimal number of comparisons needed, and by $C(n)$ the information-theoretic lower bound $\lceil \log_2 n! \rceil$. It is known that $S(n) = C(n)$ for all $n \leq 11$, but $S(n) = C(n)+1$ for $12 \leq n \leq 15$. See Peczarski's paper for references. See also A036604.