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$$.