Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!brutus.cs.uiuc.edu!apple!bionet!ames!amdcad!weitek!practic!vlsisj!davidc
From: davidc@vlsisj.VLSI.COM (David Chapman)
Newsgroups: comp.sources.wanted
Subject: Re: Looking for a better sort(1)
Summary: try a replacement selection sort
Message-ID: <15352@vlsisj.VLSI.COM>
Date: 10 Oct 89 23:54:56 GMT
References: <110@pmdvax.UUCP>
Reply-To: davidc@vlsisj.UUCP (David Chapman)
Organization: VLSI Technology Inc., San Jose, CA
Lines: 23

In article <110@pmdvax.UUCP> staylor@pmdvax.UUCP (Scott G. Taylor) writes:
>I am looking for a better sort(1) which will exploit free memory
>to increase speed.  Actually, I'm looking for one that will do
>wnything to increase speed.  My application involves sorting
>many (>500,000) records.  Has anyone written a sort which hashes 
>or otherwise speeds execution?

Try Knuth's Replacement Selection Sort, Vol. 3 p. 256.  It's the algorithm
we use to sort data (millions of records).  It works particularly well when
the time spent in comparing keys is small relative to I/O time.  When this
happens it sorts in almost linear time.

Warning: it is not an in-place sort.  You need enough disk space to hold
a temporary file the size of the data file, and possibly room for a third 
copy if you don't want to stomp on the original.

Sorry, I can't send you source code but if you have questions on how it
works I'll be glad to answer them.
-- 
		David Chapman

{known world}!decwrl!vlsisj!fndry!davidc
vlsisj!fndry!davidc@decwrl.dec.com