3 ms·

I had a feeling that O(N) is pretty impossible for the general use case.

• 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 ago
    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).
  • Xorlev 10y ago
    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.
• beagle3 10y ago
  It is impossible for comparison-based sorts; sketch of proof: there are N! different arrangements. sorting is equivalent to figuring which one of those N! arrangements we are seeing. In the worst case, each binary comparison can reduce at most, 50% of the search space. Hence the worst case may need log_2(N!) comparisons, which is O(N log N) However, it might be possible if comparisons are not essential - e.g. radix sort is (with some assumptions) O(N)