[OT] stable algorithm with complexity O(n)

[Diez B. Roggisch]

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?

Diez