sort

[Henry Spencer]

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
are sort algorithms which are considerably better (linear rather than
linear-log) in the *typical* case.  Or so I am told.
-- 
NASA is to spaceflight as the  |     Henry Spencer at U of Toronto Zoology
US government is to freedom.   | uunet!attcan!utzoo!henry henry at zoo.toronto.edu