[OT] stable algorithm with complexity O(n)

[Diez B. Roggisch]

Duncan Booth schrieb:
> "Diez B. Roggisch" <deets at nospam.web.de> wrote:
> 
>> David Hláčik schrieb:
>>> Hi guys,
>>>
>>> i am really sorry for making offtopic, hope you will not kill me, but
>>> this is for me life important problem which needs to be solved within
>>> next 12 hours..
>>>
>>> I have to create stable algorithm for sorting n numbers from interval
>>> [1,n^2] with time complexity O(n) .
>>>
>>> Can someone please give me a hint. Would be very very thankful!
>> Unless I grossly miss out on something in computer science 101, the 
>> lower bound for sorting is O(n * log_2 n). Which makes your task 
>> impossible, unless there is something to be assumed about the 
>> distribution of numbers in your sequence.
>>
>> Who has given you that assignment - a professor? Or some friend who's 
>> playing tricks on you?
>>
> I think you must have fallen asleep during CS101. The lower bound for 
> sorting where you make a two way branch at each step is O(n * log_2 n), but 
> if you can choose between k possible orderings in a single comparison you 
> can get O(n * log_k n).
> 
> To beat n * log_2 n just use a bucket sort: for numbers with a known 
> maximum you can sort them digit by digit for O(n log_k n), and if you don't 
> restrict yourself to decimal then k can be as large as you want, so for the 
> problem in question I think you can set k=n and (log_n n)==1 so you get 
> O(n)

Thanks. I *totally* forgot about that.

Diez