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

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.