comparision based sorting algorithms – Computer Science Stack Exchange

Comparison based sorting algorithms require $Omega(n log n)$ comparison (notice the big omega).

Heapsort uses $O(n log n)$ comparisons. This is not a contradiction since $Omega(n log n) cap O(n log n) neq emptyset$, i.e., there are functions of $n$ that are both in $Omega(n log n)$ and in $O(n log n)$.

To be more precise, all comparison-based algorithms must use
$$
log_2 n! ge log_2(n^n e^{-n})
= nlog n – n log_2 e
$$

comparisons, while Heapsort uses at least $n log n – n log_2 e$ comparisons (since it is a comparison-based sorting algorithm) and at most $c n log n$ comparisons for some fixed constant $c>0$.