Why can't we sort N numbers in comparison sorting algorithm faster than O(n log n) time?

Question

I was looking into binary, binomial and Fibonacci heap sort and I found out that takes O(n log n) time to sort. It would be great if someone can give me a reason as to why it is so.

Answer 1

A list of n elements has n! permutations. One of these permutations is the correctly sorted one. A single comparison between two elements conveys only 1 bit of information and therefore can't possibly do any better than cutting the search space in half. So a lower bound on the number of comparisons needed to distinguish the correctly sorted permutation from all other permutations is log2(n!) ∈ O(n log n).

Note that log2(n!) really is just a lower bound - it doesn't mean that it is actually possible to sort n number with exactly ceiling(log2(n!)) comparisons. In fact, there are permutations for which you need a few more comparisons. But this doesn't matter if we are just interested in the asymptotic behaviour.

So you see that if we don't restrict ourselves to comparison-based sorting algorithms, the lower bound doesn't hold. (See e.g. bucket sort or radix sort.)