sort

[Paul Hudson]

In article <29474 at cornell.UUCP> aitken at shamesh.cs.cornell.edu (William E. Aitken) writes:
   In article <1989Jun29.155648.28819 at utzoo.uucp> henry at utzoo.uucp (Henry Spencer) writes:
   >In article <4700040 at m.cs.uiuc.edu> kenny at 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 at moncam.co.uk,
	;"	  FAX: +44 (223) 420911		 ...!ukc!acorn!moncam!paul
 `"";";"        "/dev/null full: please empty the bit bucket"