Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cca!g-rh
From: g-rh@cca.CCA.COM (Richard Harter)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <19959@cca.CCA.COM>
Date: Fri, 18-Sep-87 11:12:29 EDT
Article-I.D.: cca.19959
Posted: Fri Sep 18 11:12:29 1987
Date-Received: Sun, 20-Sep-87 01:41:27 EDT
References: <460@naucse.UUCP>
Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 55
Summary: Insufficient information
Xref: mnetor comp.misc:1240 comp.lang.c:4404

In article <460@naucse.UUCP> sbw@naucse.UUCP (Steve Wampler) writes:
>Can anyone point me to published/public domain stable sorting
>algorithms that are reasonably time and space efficient?
>
>I have an NlogN stable sort that eats memory like cupcakes, and
>a stable sort that requires only N+C memory that barely beats
>a bubble sort.  Every try at something inbetween has resulted
>in what I consider failure - typically exemplified by no real
>gain in speed over my slow one.  I know that it can be down
>in NlogN^2 time, and that Macro SPITBOL uses a stable heapsort,
>but I don't want to spend anymore of my time on it.
>
>C code would be a nice way to describe the algorithm.
>
>Please Email me any suggestsions.

	Your requirements are vague, and it makes a real difference.
Are your talking about sorting fixed length or variable length
records?  Is the sort to be in place or is it to produce an output
array (file) with the input untouched.  Should it handle arbitrary
lengths?

	If an address calculation sort is admissable the sort can be
done O(N) with O(N) additional memory.  If O(log N) additional memory
is acceptable and an in place sort for fixed records is desired it can
be done stably in O(N log N) time.  If record sizes are variable things
are tricky.

	The best single reference that I know of is Knuth's volume III
on sorting.  I am not entirely happy with it -- there are important
techniques that are only lightly touched -- but it is comprehensive
and it does give the algorithms.

	May I suggest that you repost your request with more detail:

(a)	Is the data in memory or in a file?  If the latter are we talking
	about sorts of arbitrary length data?  If so are we talking about
	disk sorts or tape sorts?

(b)	Are you using fixed length records, or variable length records?

(c)	Are memory constraints are (1) constant, (2) log N, or (3) N?

(d)	Is it a single-key sort or multi-key?

(e)	Is address calculation admissable or not admissable.  [In address
	calculation sorts you derive a function on the key that gives
	the approximate address of a record in the sorted file.]

(f)	Is it fixed key-length or variable key length?
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.