sort

[kenny at m.cs.uiuc.edu]

Glenn Ford (uunet!ocsmd!stsim!glenn) 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.  

Depending on what you're doing, it may be to your advantage to code a
custom sort for your particular application; qsort(), while `as fast
as possible' up to the constant factor, is still rather slow (you pay
for the generality with a subroutine call for every comparison, and
lots of pointer de-references).  A non-recursive implementation of
quicksort is probably the way to go; use care in selecting the pivot
element.  You may also find it advantageous to hand-optimize the
generated code.

If your lists are close to ordered already, you may do well to use one
of the sorts that can take advantage of the ordering; Shell-Metzner
sort is one of them.  Also, if you're adding items to an
already-sorted list, you do better to sort the additions and then
merge the two lists.

There are lots of applications that are sort-bound; good luck in
achieving a reasonable running time for yours.  Sorry that there isn't
any easy way from where you are already;  a good source for ideas will
be Volume 3 of Knuth.

| /         o            Kevin Kenny                             (217) 333-5821
|<  /) |  | | |/\        Department of Computer Science           o  ,    o  ,
| \ X_  \/  | | |        University of Illinois                 40 07 N 88 13 W
kenny at cs.uiuc.edu        1304 W. Springfield Ave.       
uunet!uiucdcs!kenny      Urbana, IL   61801                  AD ASTRA PER ARDUA
k-kenny at uiuc.edu
kenny%cs at uiucvmd.bitnet