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

Hi Mike,

Very nice, but...There are at least two problems with this technique. First, it requires that all the values be integers. You cannot implement this with characters or floating point numbers. Second, it requires that they be unique. If they're not, there will be at least one instance where the sorted array doesn't contain a value. IMHO, any sorting technique of merit should be able to properly arrange the values regardless of type and range.

These are a couple of reasons why I maintain that the indirect QuickSort is still the fastest. Mike H.'s Bubble Sort fails (sorry, Mike) because of the requirement that the list already be partially ordered. If, for example, the last element in the list is the smallest, it's even less efficienct than a Selection/Exchange sort.

If anyone's interested in seeing the implementation of these three sorts (Quick, Bubble, and Selection/Exchange), I'll be happy to post. Just give me some time. It's been quite a while since I wrote a QuickSort.