
Sort Algorithm
How might someone with (much) more knowledge explain this?
A common result in the analysis of sorting algorithms is that for n elements, the best averagecase behavior of any sort algorithm—based solely on comparisons—is O(n log n).
How might a sort algorithm beat this averagecase behavior based on additional prior knowledge of the data elements?
What sort of speedup might be anticipated for such an algorithm? In other words, does it suddenly become O(n), O(n log n) or something similar?

Re: Sort Algorithm
If you are sorting nonnegative numbers and you know the maximum possible number M, then you can do as follows. Declare an array output of M elements, fill it with zeroes, go through a given array input and for each number k in input, assign 1 to the kth element of output. After that, go through output in the order of increasing (or decreasing) indices and print indices where 1 is stored. The time complexity of this algorithm is O(M). If the length of input is n and if M <= c * n for some constant c that does not depend on n and M, then the complexity is also O(n).

Re: Sort Algorithm
Thank you for that explanation emakarov! Appreciate it.