I don't get the idea... :( Does this suppose that all numbers between 1 and X are present in the source array? In this case, the algorith is useless since

for i = 1 to X
sorted[i] = i
endfor

gives the same result.

If a number can be found more than once in the source array, then the result will contain gaps.

What am I missing?

Vlad

>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.