Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!linus!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <2454@mmintl.UUCP>
Date: Mon, 5-Oct-87 20:06:16 EDT
Article-I.D.: mmintl.2454
Posted: Mon Oct  5 20:06:16 1987
Date-Received: Sat, 10-Oct-87 05:58:35 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM> <105@nusdhub.UUCP> <4791@ncoast.UUCP>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT.
Lines: 14
Xref: mnetor comp.misc:1411 comp.lang.c:4748

In article <4791@ncoast.UUCP> btb@ncoast.UUCP (Brad Banko) writes:
>somebody else commented that shellsort is not necessarily stable, but i
>don't understand why not, since essentially if you don't swap on equality
>things should stay in order, shouldn't they?

The problem is not with equality of the compared elements, but equality of
one of them with an intermediate element.  Suppose we have a 3 element
array, with keys, in order, 2, 1, and 1.  We do a Shell sort with an initial
increment of 2.  The 2 is compared with the final 1, found larger, and
swapped.  Now the 1's are out of order.
-- 

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Ashton-Tate          52 Oakland Ave North         E. Hartford, CT 06108