Newsgroups: comp.lang.c
Path: utzoo!henry
From: henry@utzoo.uucp (Henry Spencer)
Subject: Re: sort
Message-ID: <1989Jun29.155648.28819@utzoo.uucp>
Organization: U of Toronto Zoology
References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu>
Date: Thu, 29 Jun 89 15:56:48 GMT

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
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@zoo.toronto.edu