Sorting a sequence in O(n) time [duplicate]

Question

Possible Duplicate:
Sorting in linear time?

Suppose we are given a sequence S of n elements, each of which is an integer in the range [0,n^2-1]. Can we sort it in O(n) time?

Please dont mind me asking too many interview questions. I am just appetent.

Answer 1

No.

When the only precondition is an integer in the range 0-N².

• Counting sorts won't work because the scanning, be it bit-patterns for distinct inputs or buckets for duplicate inputs, would complete in O(N²)
• The range would make the key length for radix sort dependent on N hence radix won't work in O(N).

Any statement involving "When N is small" invalidates any O based argument.