Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.misc Subject: Re: A very brief history of optimal sorting methods Message-ID: <4371@goanna.cs.rmit.oz.au> 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 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.