Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!ames!haven!decuac!bacchus.pa.dec.com!granite.pa.dec.com!mwm From: mwm@fenris.relay.pa.dec.com (Mike (My Watch Has Windows) Meyer) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Message-ID: Date: 27 Nov 90 01:44:30 GMT References: <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP> <4371@goanna.cs.rmit.oz.au> Sender: news@wrl.dec.com (News) Organization: Missionaria Phonibalonica Lines: 65 In-Reply-To: ok@goanna.cs.rmit.oz.au's message of 26 Nov 90 09:15:01 GMT In article <4371@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: Path: bacchus.pa.dec.com!shlump.nac.dec.com!decuk.uvo.dec.com!decuac!haven!udel!wuarchive!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.misc Date: 26 Nov 90 09:15:01 GMT References: <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 25 In article , mwm@raven.relay.pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: > In article <24945:Nov1218:54:5590@kramden.acf.nyu.edu> > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > Sorting is linear in the number of bytes being sorted. This is true both > theoretically and practically. > Rather than arguing theory, I'll just ask for proof. How about making > available sources to either 1) a plug-compatible replacement for > qsort(3) or 2) a replacement for sort(1), so we can try some test > cases and see how they work, and how well they work. 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. After all, what's left if after you exclude sorting fixed records & arbitrary strings of bytes with termination bytes? That's why I gave both options - to allow as much flexibility as possible. Dan quite politely offered still-under-construction source for a routine that is to radix sorting what qsort is to comparison sorting. It would be quite easy to turn that routine into a primitive version of sort(1), but (as expected) impossible to turn it into anything that looks like qsort(3). Nobody is denying that the O(N.lg N) bound applies to COMPARISON-BASED sorting methods. Bernstein's point is that not all sorting methods are comparison-based. The interface of qsort() is a comparison-based interface: qsort() is passed a comparison function and is _not_ passed the kind of information that the linear-expected-time methods I know of (apparently not quite the same as what Bernstein is talking about) need. Yup. So tell me what about sort(1) is comparison based? Not having seen his code, I asked for things I could use. Just because I don't think he can implement a qsort interface for a radix sort doesn't mean he can't. That's a testable interface, so give that as an option. It only hurts if someone doesn't read the entire paragraph. 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 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.