|
|
|
|
|
|
by beagle3
3455 days 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) |
|
|