Re: A very brief history of optimal sorting methods

Article View: comp.lang.misc

Article #2134

#2134

From: Mike (My Watch Has Windows) Meye...
Date: Fri, 16 Nov 1990 19:41

15 lines
1332 bytes

   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.

While obviously true in some situations (but I can do O(1) sorting in
"some" situations), this goes against the grain for the general case.

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.

	<mike
--

Technical Details

Message-ID: <MWM.90Nov16144102@raven.relay.pa.dec.com>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!udel!haven!decuac!bacchus.pa.dec.com!bacchus!mwm

References:

<6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP> <4248@goanna.cs.rmit.oz.au> <24945:Nov1218:54:5590@kramden.acf.nyu.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!udel!haven!decuac!bacchus.pa.dec.com!bacchus!mwm
From: mwm@raven.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: <MWM.90Nov16144102@raven.relay.pa.dec.com>
Date: 16 Nov 90 19:41:02 GMT
References: <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <237@smds.UUCP>
 <4248@goanna.cs.rmit.oz.au> <24945:Nov1218:54:5590@kramden.acf.nyu.edu>
Sender: news@wrl.dec.com (News)
Organization: Missionaria Phonibalonica
Lines: 15
In-Reply-To: brnstnd@kramden.acf.nyu.edu's message of 12 Nov 90 18:54:55 GMT

Reply to Parent Message