comparision based sorting algorithms

Question

The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a comparision based algorithm?

Answer 1

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}) = n\log 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$.