Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!csd4.milw.wisc.edu!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!kenny
From: kenny@m.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: sort
Message-ID: <4700040@m.cs.uiuc.edu>
Date: 28 Jun 89 01:28:00 GMT
References: <166@stsim.UUCP>
Lines: 36
Nf-ID: #R:stsim.UUCP:166:m.cs.uiuc.edu:4700040:000:1731
Nf-From: m.cs.uiuc.edu!kenny    Jun 27 20:28:00 1989


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@cs.uiuc.edu        1304 W. Springfield Ave.       
uunet!uiucdcs!kenny      Urbana, IL   61801                  AD ASTRA PER ARDUA
k-kenny@uiuc.edu
kenny%cs@uiucvmd.bitnet