Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!usc!cs.utexas.edu!uunet!mcvax!ukc!acorn!moncam!paul
From: paul@moncam.co.uk (Paul Hudson)
Newsgroups: comp.lang.c
Subject: Re: sort
Message-ID: <PAUL.89Jun30120758@marvin.moncam.co.uk>
Date: 30 Jun 89 11:07:58 GMT
References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu>
	<1989Jun29.155648.28819@utzoo.uucp> <29474@cornell.UUCP>
Sender: paul@moncam.co.uk
Organization: Monotype ADG, Cambridge, UK.
Lines: 22
In-reply-to: aitken@shamesh.cs.cornell.edu's message of 29 Jun 89 17:53:48 GMT

In article <29474@cornell.UUCP> aitken@shamesh.cs.cornell.edu (William E. Aitken) writes:
   In article <1989Jun29.155648.28819@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes:
   >In article <4700040@m.cs.uiuc.edu> kenny@m.cs.uiuc.edu writes:
   >>>Does anyone have a sort routine (in memory sort) faster than quicksort, of
   >>>so please e-mail it to me, thanks.
   >>
   >>Generally speaking, there isn't any; at least, no sort can be faster
   >>than quicksort by more than a constant factor on a von Neumann machine.  
   >
   >There is an important phrase missing here:  "in the worst case".  There

   No.  One of quicksort's problems is its horrendous worst case behavior :
   quadratic.  It's rather easy to find sorts that are faster than quicksort

However using a median-of-three pivot makes the worst case *extremely*
unlikely. See Sedgewick "Algorithms". 

--
Paul Hudson	 MAIL: Monotype ADG, Science Park, Cambridge, CB4 4FQ, UK.
		PHONE: +44 (223) 420018	  EMAIL: paul@moncam.co.uk,
	;"	  FAX: +44 (223) 420911		 ...!ukc!acorn!moncam!paul
 `"";";"        "/dev/null full: please empty the bit bucket"