My first thought was a radix sort, but since that does depend on the value of the largest number, I'm don't think that it's strictly O(N) in this case.

I have tried Radix Sort, but since the number of digits is not fixed, it scales with size of input, due to that fact, in this case, the complexity would be O(nlogn), since log(base10)n is the amount of digits.

Yeah, that's what I was thinking too. Even counting sort depends on the range of values, so it wouldn't fit either. I'm out of ideas, sorry

Thanks for the reply, nonetheless.

If anyone else could chime in, I would be rather thankful.

http://en.wikipedia.org/wiki/Sorting_algorithm

While I thank you for the reply - I already read the wikipedia entry for that, twice. I also spent a few hours on google, and reading "Introduction To Algorithms" (One of the authors is Cormen, another is Rivest, another is Stein, I don't recall the last one).

Any other ideas folks ?

>> You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.

2 questions to understand the question:

1. Why does the range of value matter? (size/range of value would have no impact on the order of algorithm from what I know)
2. When you say "in O(N) time" do you mean it's an algorithm of order N or you really mean some number of mili/micro/seconds.. ?

1. It does affect algorithm runtime in several cases, especially when dealing with non-comparison based sorts (since it's proven that comparision based sorts cannot be guaranteed to run in better than O(n log n) time, they don't make the cut for this problem). Look at some of the sorts already mentioned in this thread.

2. Linear time with respect to the length of the input.

Have you tried out SmoothSort ?

Its best case is O(n) and worst case is O(n log(n)) with the obvious downfall of difficult to implement.