Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!phri!dasys1!wfp
From: wfp@dasys1.UUCP (William Phillips)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <1351@dasys1.UUCP>
Date: Tue, 22-Sep-87 01:20:41 EDT
Article-I.D.: dasys1.1351
Posted: Tue Sep 22 01:20:41 1987
Date-Received: Thu, 24-Sep-87 03:32:41 EDT
References: <460@naucse.UUCP> <1719@ho95e.ATT.COM>
Organization: The Big Electric Cat
Lines: 31
Summary: Shell sort in _Software Tools_
Xref: mnetor comp.misc:1281 comp.lang.c:4482

In article <1719@ho95e.ATT.COM>, wcs@ho95e.ATT.COM (Bill.Stewart) writes:
> 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?
> 	....
> 
> :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.


It's even easier to translate Ratfor (or Pascal) into C,
and there is a very workable Shell sort in _Software Tools_
(or _Software Tools in Pascal_) by Kernighan and Plauger.

I translated it into assembler for a mini back in
1977, and it was still in use on that system in 1987
(a very durable sort, I think)!  The Shell sort is easy
to understand (therefore to debug), reasonably
fast (not the fastest, but respectable), and about as 
compact as you could want.


-- 
William Phillips                 {allegra,philabs,cmcl2}!phri\
Big Electric Cat Public Unix           {bellcore,cmcl2}!cucard!dasys1!wfp
New York, NY, USA                (-: Just say "NO" to OS/2! :-)