Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!sun-barr!decwrl!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.c
Subject: Re: sort
Message-ID: <6030@goofy.megatest.UUCP>
Date: 30 Jun 89 00:47:09 GMT
References: <1989Jun29.155648.28819@utzoo.uucp>
Organization: Megatest Corporation, San Jose, Ca
Lines: 16

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.  


Where'd you come up with that? If you can spare the memory for it, a bucket sort,
with a bucket for each key, is O(n), not O(n-log-n). You can make trade-offs
between speed and memory usage with mixed methods. Besides, there are considerations
of average-case vs. worst-case. The relative costs of internal and external
memory access and key comparison also matters.

The subject of sorting has been (ahem) hashed over perhaps as much as any
other in the field of computers. Why not "open book before engaging mouth"? :-)