Sorting algorithm problem

Here's a brain teaser that's been on my mind for a few days.

We have a sequence S of n elements. Each element is an integer in the range [0, n^2-1]. Describe a simple method for sorting S 开发者_如何学JAVAin O(n) time.

Probably something obvious that I am just missing, but I'd appreciate any insight.

---

Bucket Sort!

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

---

Radix Sort! (which is just a special case of bucket sort.)

---

Write in base n and do a bucket sort, by doing a counting sort for each bucket (buckets correspond to digits in base n).

O(n) time, O(n) space.

---

Quicksort is O(n log n), as the standard "good algo" way to sort a list. So there has to be some kind of "trick" to get down to O(n) time.

The only real trick to this data is it goes from 0 to n^2-1... but I can't think of how this could be used to sort in O(n) time....

P.S. Sounds like homework, not something you would "puzzle on for the sake of knowledge"

P.P.S. I fail for not thinking of bucket sort.