Some simple theorems on incremental sorting

Some simple theorems on incremental sorting

A standard component of many in situ sorting algo-

\operatorname {o r d}. x. y = \text {i f} x > y \rightarrow x, y := y, x \nsubseteq y \rightarrow s k i p f _ {i} {x ≤ y },

i.e. swapping two values if and only if they are out of order or, in other words, removing an inversion if present. I shall represent the operation ord.x.y by

x \rightarrow y

i.e. a dotted arrow from x to y .

We are interested in other pairs, whose being in order is not destroyed by a collection of ord operations; if , with usv, (u,v) is such a pair, we shall denote it by

u \rightarrow v,

i.e. a drawn arrow from u to v

In the following pictorial representation of some theorems there is no aliasing, i.e. different nodes of the graph correspond to different variables.

\underline {{\mathrm {L e m m a}}} 0 u \rightarrow v x \rightarrow y

Proof 0 The ord operations involve $x$ and $y$ only, in particular $u$ and $v$ are not involved and their order is maintained. (End of Proof 0.)

\xlongequal {\mathrm {L e m m a 1}} \begin{array}{l} u \longrightarrow y \ x ^ {\prime} \longrightarrow v \end{array}

Proof.1 Operation ord. x.y neither increases x, nor decreases y ; From the constancy of u and v the conclusion now follows. (End of Proof 1).

Lemma 2

Proof2 Initially, the maximum is an element of ${a,A}$ , hence $A$ finally equals the maximum and hence $B \rightarrow A$ is not destroyed; similarly, the minimum is initially an element of ${b,B}$ and hence finally equal to $b$ , and therefore $b \rightarrow a$ is not destroyed (End of Proof2)

Note that it is essential that both ord. a. A and ord. b. B are executed. Lemma 2 is the most interesting of all. The single arrows $\mathbf{b} \rightarrow \mathbf{a}$ and $\mathbf{B} \rightarrow \mathbf{A}$ can be extended to arbitrary congruent directed graphs, provided ord.x.x is executed between each pair of corresponding variables.

Lemma 3

Proof3 The value of $b$ is the minimum 2 the value of $a$ is the maximum. (End of Proof 3.)

As special consequence we mention

Lemma 4

and

Lemma 5

From Lemmata 2 and 5 it follows that 4 elements can be sorted by a sequence of 5 ord's:

ord.0.2 & ord.1.3 ; ord.0.1 & ord.2.3 ; ord.1.2

As ${2}^{4} < 4! < {2}^{5}$ ,5 ord's is indeed the minimum.

So much for my simple theorems. Needless to say that my feelings about their pictorial representation are very mixed.

Austin, 2 September 1985

prof. dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 United States of America