# comparision based sorting algorithms

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?

## 1 Answer

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

• Many thanks dear @Steven for the great explanation!!!! Jul 19, 2021 at 15:03