🚀 go-pugleaf

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

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.

-- 
I am not now and never have been a member of Mensa.		-- Ariadne.