sort

[michael.p.lindner]

In article <4700040 at m.cs.uiuc.edu>, kenny at m.cs.uiuc.edu writes:
> 
> Glenn Ford (uunet!ocsmd!stsim!glenn) writes:
> >Does anyone have a sort routine (in memory sort) faster than quicksort, of
> 
> 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.  
	...

Of COURSE a sort can be faster than quicksort.  First of all, quicksort has
problems with data which is already close to being sorted.  There are sorts
which are consistently N log N no matter WHAT shape the data is in, such as
a merge sort.  Then there's the radix sort, which is N log (number of bits
in key).  Which sort is best depend on the data.  I refer Glenn to Donald E.
Knuth's book "Searching and Sorting," considered by many to be the definitive
sorting algorithm book.  If he's just looking for an implementation, well,
I have some, but I signed an intellectual property agreement with my
employer, so he'll need permission from Bell Labs to get it from me, but
I'm sure someone out there has a radix sort or some such that they'd share
with us.

Mike Lindner
attunix!mpl
AT&T Bell Laboratories
190 River Rd.
Summit, NJ 07901