[oops, left off the magic colon]


A few more notes on my previous post on this topic.

Obviously this technique involves looking at each key exactly 5 times, and
swapping about half the elements (I think). Note that this makes this sort
O(n), or linear in time with respect to the size of the input.

Instead of the recursive technique, I think you could sort (partition) first
on the _least_ significant bit of the key and then on successively more
significant bits. This is of course, the binary equivalent of the way they
used to sort punched cards.

Here is how you would sort a stack of punched cards on a 3 digit field:

1: Sort on the _least_ significant digit. This puts all the xx0 cards in one
pocket, the xx1 cards in another, etc.

2: Stack the cards back up, with the xx0 cards first, the xx1 cards next,
etc.

3: Sort again on the middle digit. This puts all the x0x cards in one
pocket, the x1x cards in the second, etc. Note that in any pocket, the cards
are still in correct order by the _least_ signigicant digit because card
sorting is stable (ie: the order in the output bins is the same as the order
in the input).

3: Stack 'em back up, 0x0 first, 0x1 next, etc.

4: Sort on the most significant digit. Now we have all the 0xx cards in one
pocket, the 1xx in the second, etc. Note that within a pocket everything is
still in order on the low two digits.

5: Stack 'em back up one more time 0xx first, 1xx next, etc.

6: Done!


Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.