stable algorithm with complexity O(n)

[Cameron Simpson]

On 13Dec2008 19:22, David Hl??ik <david at hlacik.eu> wrote:
| 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) .

Since sorting in general is O(n log n), I don't see how you're going to
do in in O(n) unless there's something special about your number range
you've not told us about. A stable sort limits your choices somewhat
more, but not a lot - it usually just imposes a little more care on the
comparison stage for most algorithms.

I think you need to define the problem in more detail.
-- 
Cameron Simpson <cs at zip.com.au> DoD#743
http://www.cskk.ezoshosting.com/cs/

Newtons 4th law:
    For every action there is an equal and opposite beaureaucratic policy.
        - Adrian Tritschler, ajft at cs.adfa.oz.au