Path: 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


   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
--