[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.