Specific Sorting Algorithm Trouble

Sup /prog/,

So, I'm having trouble finding out what my professor meant by this, not sure if it's a typo because he often has typo's in his assignments. If the range was simply 1 to m, I would just use counting or bucket sort, but since it's 1 to m^2, I really have no clue. Thanks for any help I can get on this. Here's the problem:

Let x1, x2,…,xn be a sequence of integers in the range 1 to m^2. Describe an algorithm to sort this sequence in time O(n + m).

I hope this post doesn't go to the top, it's been a while and I forgot the email conventions.

Anyways, I was thinking possible a radix sort using bucket sort would work, but I'm not quite sure what my radix would be. Any elaboration on this would help, thanks.

>>2
try picking a radix and then try proving that the algorithm will run in O(n + m)

Sleep sort

>>3
Hmm, I'll try this. I'm thinking maybe a radix of log(m) or something. Thanks for the tip.

>>4
Weird, I'd never heard of this. I'll check it out thanks.

>>4
Haha, this is the coolest sorting algorithm I've ever come across, if I can't figure this one out(with radix), I'm going to do sleep sort. I doubt my prof. has even heard of it.

>>6
zomg it actually works for this!

>>8
Actually it doesn't, I just realized.

Let m = 5, and Arr = [1, m^2] = [1, 25]

It will take 25 seconds, and thats just including the sleeping, what about the time we spend running through the array making new threads? It needs to run in O(n + m), radix sort is the only way as far as I know.

>>9
just have the ith thread time out after sqrt(i) seconds, on a machine with infinite precision time.

>>9
You don't have to use seconds. Just don't use something too short.

>>10
>>11

It doesn't matter what unit of time you use, this is asymptotic notation, constants don't apply. O(10000000) is the same as O(1).

>>12
yesh. Thish ish y ey treds hime oot afta f(n) secounds, wher f(n) in o(n).