Yep, the pigeonhole sort <g> (known to any mailroom clerk). It doesn't really require any comparisons. It takes a single pass through the source and stores the values with only one move each. Any other sorting technique compares elements against other elements potentially "moving" all elements more than once.

Its horribly space inefficient as it requires storage for the original list and the sorted. The code is really easy...

Given x element array containing unsorted numbers ranging 1-x (source[x]) and storage array (sorted[x]),

If this code doesn't run, its because I wrote it off the top of my head. You'll get the general idea though.

local x
x = 1000
local array source[x],sorted[x]
local i

*Fill in the source array
for i = 1 to x
source[i] = int(rand(1)*x)+1
endfor

*Now sort the array
for i = 1 to x
sorted[source[i]] = source[i]
endfor

Of course, this is only of interest when the professors didn't know this technique at all.