Lower bound for asymptotic time of sorting algorithms

Question

I am dabbling in sorting algorithms in my Algorithms course in university.

Is there any proof for a lower bound on the asymptotic time cost of a sorting algorithm?

Or, to word my question differently, do we know whether it is possible to sort N elements faster than $N\log (N)$?

Answer 1

I assume you mean comparison-based. First, there are $n!$ permutations of the given input. One comparison halves the numbers of permutations so one definitely has to do $log_2(n!)$ comparisons, also know as $n*log_2(n)$.

Now, there are many situations where one could do significantly* better but requires some knowledge of the input data. Some examples are sorting, say, 64-bit integers, bounded integers or partial sorted input.

*significantly is a bit relative here: $n*log_2(n)$ is already plenty fast.