5 answers
4
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of$n$$n^2$$n \log n$$n \log^2n$