Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!noao!arizona!naucse!sbw
From: sbw@naucse.UUCP (Steve Wampler)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <461@naucse.UUCP>
Date: Sun, 20-Sep-87 09:24:37 EDT
Article-I.D.: naucse.461
Posted: Sun Sep 20 09:24:37 1987
Date-Received: Tue, 22-Sep-87 01:28:32 EDT
References: <460@naucse.UUCP> <19959@cca.CCA.COM>
Organization: Northern Arizona University, Flagstaff, Arizona
Lines: 49
Summary: Ok, here's more information
Xref: mnetor comp.misc:1267 comp.lang.c:4463


It was requested that I provide more information on my needs, so:

I want a stable, minimum storage sort that takes exactly the
same arguments as qsort (section 3 of the UNIX man pages).
It should be reasonably fast (i.e. not N^2).

Now, I have some requests of my own.  I'm sorry if this offends
anyone, but it's rather bothersome to have to wade through the
pages of misinformation I've been getting.

Please don't respond unless you:

	(1) Know what 'stable' means in terms of sorts.

	(2) Know what 'minimum storage' means.

	(3) Know of a fast algorithm that meets those
	    criteria.

None of the following basic sorting techniques meets (1) and/or (2)
above:

	Shell, Quick, Heap.

Any sort can be made stable, the question is at what cost.

Please don't quote timings from Knuth for me.  For that matter,
please don't refer me to Knuth.  While it is the best reference
around for sorting techniques, the discussion of stableness is
minimal, being confined to exercises throughout the text.  He
does give a hint on writing a NlogNlogN minimal storage stable
sort, but that's all, a hint.  I am well aware of what Knuth
and the majority of data structure texts have to say about stable
sorts.

The only published (and reasonably fast) stable sorting algorithm
I know about runs in N^(3/2) times (excuse me, stable *and* requiring
minimal storage).  I am hoping for something faster.

Remember, in my original posting, I stated that I have an NlogN
stable sort that isn't minimal storage (it takes N+N storage, as
do most of the obvious such beasties).  It's rather trivial to
modify a quick sort to do that (it's even more trivial to modify
a merge sort to be stable - but not to have be minimal in storage).

Please don't offer 'solutions' unless you know them to be just that.

Thanks.