🚀 go-pugleaf

In article <MWM.90Nov26194430@fenris.relay.pa.dec.com> mwm@fenris.relay.pa.dec.com (Mike (My Watch Has Windows) Meyer) writes:
>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. Since the
>former are very popular on unix, and the latter are rare, it's a nice
>addition to the unix libraries. But it won't replace quicksort.

I don't understand.

You claim Dan's code _does_ sort in linear time, but only for
"arbitrary strings with termination bytes". I take this to mean a
Unix-like file system where each record is null-terminated.

You then claim that code cannot handle "records with fixed-length
keys holding arbitary data". It is unclear why "fixed-length" gets
into the act. Surely it is linear time to add a termination-byte to
each string! So I assume you mean Dan's code does not work for "keys
holding arbitary data" - in other words, a compare routine is needed
to order any two keys. This is of course, a known property that Dan
(and others) specified as a requiremet.

>
>I do think Dan is wrong for picking on computer scientists. It doesn't
>do anything they say can't be done; it just uses a known special case
>in a way that is very broadly applicable on Unix.

I agree Dan is probably tweeking many noses (and was not very gentle
about it), but you just certified Dan to be right!

Stanley Chow        BitNet:  schow@BNR.CA
BNR		    UUCP:    ..!uunet!bnrgate!bcarh185!schow
(613) 763-2831               ..!psuvax1!BNR.CA.bitnet!schow
Me? Represent other people? Don't make them laugh so hard.