Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!amdcad!ames!ucbcad!ucbvax!sdcsvax!ucsdhub!jack!man!nu3b2!nusdhub!rwhite
From: rwhite@nusdhub.UUCP (Robert C. White Jr.)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <105@nusdhub.UUCP>
Date: Tue, 22-Sep-87 19:49:40 EDT
Article-I.D.: nusdhub.105
Posted: Tue Sep 22 19:49:40 1987
Date-Received: Wed, 30-Sep-87 04:33:44 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM>
Organization: National University, San Diego
Lines: 25
Summary: Stability
Xref: mnetor comp.misc:1358 comp.lang.c:4620

In article <20029@cca.CCA.COM>, g-rh@cca.CCA.COM (Richard Harter) writes:
> 	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.


	Use something we called duplicity:

	make an array of pointers to sctuctures....
	each structure contains a pointer to a copy of
		the key value and a pointer to the same
		type of sctucture [recursive].
	read each value into a structure with any duplicates
		being pushed into a linked list built on the
		last element of the sctucture [the pointer]
	pointer-sort the aray by your favorite method.
	write each aray element in order to the output with
		any linked list entries printed in linked order.

The value must have either refrences to record numbers [disk-to-disk]
or aray indices which represent the full data record.  This sort
list header method is fast and easy to implement by any fast and dirty
sort algorythm.  the linked lists provide sthe stability.

Rob ("so who asked you anyway?") white.