Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!umd5!mimsy!oddjob!hao!noao!arizona!naucse!sbw
From: sbw@naucse.UUCP (Steve Wampler)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <466@naucse.UUCP>
Date: Tue, 6-Oct-87 18:54:19 EDT
Article-I.D.: naucse.466
Posted: Tue Oct  6 18:54:19 1987
Date-Received: Sat, 10-Oct-87 19:27:14 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM> <4791@ncoast.UUCP>
Organization: Northern Arizona University, Flagstaff, Arizona
Lines: 24
Summary: Why the Shell sort isn't stable (he claims)
Xref: mnetor comp.misc:1423 comp.lang.c:4766

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 arises from the fact that in all but the last pass of the
Shell sort, you are comparing elements that aren't adjacent.  Exchanging
two non-adjacent elements runs the risk that you are changing the
relative positions of one of them with a equal-keyed element inbetween.

For example, consider the following comparison of e1 and e2:

	3 1 4 1 5 9
        ^     ^
       e1    e2

Exchanging them yields:

	1 1 4 3 5 9
        ^     ^
       e2    e1

but you've just changed the relative positions of the two elements
keyed with value '1'.