Path: utzoo!utgpu!cunews!bnrgate!bigsur!bnr-rsc!bcarh185!schow From: schow@bcarh185.bnr.ca (Stanley T.H. Chow) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Message-ID: <3766@bnr-rsc.UUCP> Date: 29 Nov 90 19:02:57 GMT References: Sender: news@bnr-rsc.UUCP Reply-To: bcarh185!schow@bnr-rsc.UUCP (Stanley T.H. Chow) Organization: BNR Ottawa, Canada Lines: 35 Summary: Followup-To: Keywords: In article 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.