sort
William E. Aitken
aitken at shamesh.cs.cornell.edu
Fri Jun 30 03:53:48 AEST 1989
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 ==============
More information about the Comp.lang.c
mailing list