🚀 go-pugleaf

In article <MWM.90Nov26194430@fenris.relay.pa.dec.com> mwm@fenris.relay.pa.dec.com (Mike (My Watch Has Windows) Meyer) writes:
> In article <4371@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>    Let me paraphrase this:
>        Dan Bernstein:	you can run faster if you don't wear blinkers
>        Mike Meyer:		prove it wearing these blinkers
> Oh, horse pucky. If the sorting method in question can't be turned
> into one of the two options I list, then it's basically worthless.

I have to agree with Mike here: if a supposedly general sorting method
can't at least be used to implement sort(1) (efficiently), it's
pointless.

> As for at the code Dan let me have, it's a very well-designed (and,
> for the most part, written) MSD radix sort. As such, it will indeed
> sort arbitrary strings with termination bytes in time linear in the
> number of bytes to sort. In it's current form, it can't be used to
> sort records with fixed-length keys holding arbitrary data.

Well, yeah, I'm still working on it. I'll make the final sort(1) clone
available ASAP.

The right way to apply radix sort (or, in fact, almost any other sort)
to your fixed-length records or other data structures inside a generic
program is as follows:

  1. Extract out of the structures some lexically ordered key. Append to
     each key some index to the original structure, or the entire
     original structure.
  2. Apply radixsort() to the keys.
  3. Sweep through the sorted keys, reordering the structures.

You can use escape characters (255 1 represents 255, 255 2 represents 0)
to handle the limited character set.

---Dan