🚀 go-pugleaf

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> <MWM.90Nov16144102@raven.relay.pa.dec.com>
   Organization: Comp Sci, RMIT, Melbourne, Australia
   Lines: 25

   In article <MWM.90Nov16144102@raven.relay.pa.dec.com>,
   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.

	<mike
--