sort

[William E. Aitken]

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
in the worst case.  Merge sort and Shell sort come to mind.



William E. Aitken <aitken at cs.cornell.edu>   | On Earth it is considered 
{uw-beaver,rochester,decvax}!cornell!aitken | ill mannered to kill your
Home: (607) 273-7810 Away : (607) 255-9206  | friends while commiting suicide
============================================*============= Avon ==============