Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!oddjob!gargoyle!ihnp4!ho95e!wcs
From: wcs@ho95e.ATT.COM (Bill.Stewart)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <1719@ho95e.ATT.COM>
Date: Sat, 19-Sep-87 00:59:24 EDT
Article-I.D.: ho95e.1719
Posted: Sat Sep 19 00:59:24 1987
Date-Received: Sun, 20-Sep-87 11:28:09 EDT
References: <460@naucse.UUCP>
Reply-To: wcs@ho95e.UUCP (46133-Bill.Stewart,2G218,x0705,)
Organization: AT&T Bell Labs 46133, Holmdel, NJ
Lines: 18
Xref: mnetor comp.misc:1248 comp.lang.c:4426

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 [big-memory fast and small-memory slow algorithms]....
	If memory serves me correctly, isn't the Shell sort stable?
	Check out the volume of Knuth that deals with sorting and
	searching.  The analysis of run-time is quite interesting,
	but basically it's around nlogn or maybe n**1.5, and it's
	about as small and simple as bubble-sort.

:C code would be a nice way to describe the algorithm.
	Well, you won't find C code in Knuth; there's "English" and
	probably MIX (not even ALGOL, which was the politically correct
	language to describe algorithms in at the time.)  But it's not
	that hard to translate into C.
-- 
#				Thanks;
# Bill Stewart, AT&T Bell Labs 2G218, Holmdel NJ 1-201-949-0705 ihnp4!ho95c!wc(