# Sort Algorithm

• Mar 27th 2013, 10:46 PM
rhymin
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 average-case behavior of any sort algorithm—based solely on comparisons—is O(n log n).

How might a sort algorithm beat this average-case behavior based on additional prior knowledge of the data elements?

What sort of speed-up might be anticipated for such an algorithm? In other words, does it suddenly become O(n), O(n log n) or something similar?
• Mar 28th 2013, 01:48 AM
emakarov
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).
• Mar 28th 2013, 11:42 AM
rhymin
Re: Sort Algorithm
Thank you for that explanation emakarov! Appreciate it.