stable algorithm with complexity O(n)

[Aaron Brady]

On Dec 13, 1:17 pm, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> "Diez B. Roggisch" <de... 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)

Minor detail: with k= n, you have log_n (n^2)= 2, so you get O(2n)= O
(n).  Same answer.

The generic sort theorems also assume you can compare arbitrarily
large numbers in constant time, which isn't true.  That is, for any
given machine, there exist numbers that you can't compare on them in
constant time.  But with a known upper bound k, you can just use a k-
bit machine.

<rhetorical>So, what's the group policy on helping with homework?  </
rhetorical>