Lower Bound for Comparison Sorts

Comparison-based sorts can only compare pairs of elements. Each comparison has $2$ outcomes (less or greater). With $n!$ possible orderings, you need at least $\log_2(n!)$ comparisons to distinguish them all.

Stirling's approximation: $\log_2(n!) \approx n \log_2 n$

So any comparison-based sort needs $\Omega(n \log n)$ comparisons in the worst case.

This is a lower bound, not an upper bound. You cannot do better than $O(n \log n)$ with comparisons alone.

Escape hatch: Non-comparison sorts (counting sort, radix sort) avoid comparisons entirely. They can achieve $O(n)$ when the data has special properties.