Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!att!cbnewsl!mpl
From: mpl@cbnewsl.ATT.COM (michael.p.lindner)
Newsgroups: comp.lang.c
Subject: Re: sort
Summary: faster than qsort? SURE!
Message-ID: <950@cbnewsl.ATT.COM>
Date: 29 Jun 89 13:58:53 GMT
References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu>
Organization: AT&T Bell Laboratories
Lines: 27

In article <4700040@m.cs.uiuc.edu>, kenny@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