2 ms·
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
by raverbashing 10y ago
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
- maweki 10y agoYou 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).
- Xorlev 10y agoIt'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.