[raverbashing]

I think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm

Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings

[Xorlev]

It's not impossible to have a O(N) sorting algorithm if you add more constraints, e.g. use operations other than comparisons.

Most people would be fine with a hybrid radix sort for day to day use.

[maweki]

You only ever have to move every element once to get a (pre-known) permutation that represents the sorted list.

The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).