[OT] stable algorithm with complexity O(n)

[MRAB]

Diez B. Roggisch 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'm assuming that the numbers are integers. I can think of an O(n) 
algorithm for this particular problem provided that n isn't huge, but if 
it's your assignment then it's up to you to discover it.