Comparison Sorting Algorithm Complexity

Question

Why is the lower bound for the time complexity of comparison-based sort algorithms O(n log n)?

Answer 1

http://en.wikipedia.org/wiki/Comparison%5Fsort#Number%5Fof%5Fcomparisons%5Frequired%5Fto%5Fsort%5Fa%5Flist

answers that question quite well, I think.

Answer 2

In short, because you must look at every element which is O(n). For each of those elements you look at, you must find out if its in the right order, which is at best O(log n) (binary search for example). So the net sum becomes O(n log n)