Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!adm!RMRichardson.PA@Xerox.COM
From: RMRichardson.PA@Xerox.COM (Rich)
Newsgroups: comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <9422@brl-adm.ARPA>
Date: Mon, 21-Sep-87 21:31:45 EDT
Article-I.D.: brl-adm.9422
Posted: Mon Sep 21 21:31:45 1987
Date-Received: Wed, 23-Sep-87 05:02:39 EDT
Sender: news@brl-adm.ARPA
Lines: 19

From: "Bill.Stewart" <wcs@ho95e.ATT.COM>
> 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.

No, the Shell sort is not *necessarily* stable.  The Shell sort is, 
in fact, a series of "sort by insertion" passes over the data, each 
sort being stable.  However, the different passes interleave the 
strings of data such that you cannot guarantee the final result will 
be stable.  

Note: the last pass of a Shell sort is a full sort by insertion 
looking at each item in the list.  It is more efficient than normally
because the previous passes have put the total list in "almost" sorted 
order.  

Rich