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: <20029@cca.CCA.COM>
Date: Sun, 20-Sep-87 16:18:04 EDT
Article-I.D.: cca.20029
Posted: Sun Sep 20 16:18:04 1987
Date-Received: Sun, 20-Sep-87 22:56:33 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu>
Reply-To: g-rh@CCA.CCA.COM.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 24
Xref: mnetor comp.misc:1262 comp.lang.c:4447

In article <3603@venera.isi.edu> lmiller@venera.isi.edu.UUCP (Larry Miller) writes:
>
>Why is STABLE necessary?  Most any NlogN routine can be written to
>swap pointers rather than the data itself, so a stable routine shouldn't
>be that important...

	STABLE:  A sort is stable if all records with the same key are
	in the same order in the output file as they were in the input
	file.

Stability is essential for sorting on multiple keys.  There are many other
applications where stability is desirable.  Using swap pointers does not
resolve the problem [I will leave it as an exercise for the reader to
determine why not.]

Incidentally, quicksort can be converted into a stable sort at a price
in time without marker bits.  The trick is to make a first pass to
calculate the size of the partitions and load each partition from the
front.
-- 

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