Smoothsort, an alternative for sorting in situ

Smoothsort, an alternative for sorting in situ.

Heapsort [0][1] is an efficient algorithm for sorting $m$ (i: 0.5 i < N) in situ ; some, however, consider it a disadvantage of heapsort that it absolutely fails to exploit the circumstances in which the sequence is initially nearly sorted. While sharing with heapsort its $N \cdot \log N$ characteristic, smoothsort does not share this disadvantage : when the sequence is sorted to start with , no rearrangement whatsoever takes place. For brevity's sake we shall describe sorting the integer sequence $m$ (i: Xs i $< X + N$ ) in ascending order.

Projected on variables $q$ and $r$ ,smoothsort is

\begin{array}{l} \begin{array}{r} \mathbb {I} [ q, r: \mathrm {i n t}; q, r := 1, X \end{array} \ \begin{array}{l}\vdots \underline {{d o}} q ≠ N \rightarrow q, r := q + 1, r + 1 \underline {{o d}}\{\text {i n v a r i a n t} P _ {0}:\end{array} \ (\underline {{A}} i, j: X ≤ i < j ∧ X + q ≤ j < X + N: m (i) ≤ m (j)) } \ ; \underline {{d o}} q ≠ 1 \rightarrow q, r := q - 1, r - 1 \underline {{o d}} \ \end{array}

The rest of smoothsort is devoted to ensuring that, for the sake of the invariance of $P_0$ ,

${R}{1} : \left( {{A}{i} : X ≤ i ≤ r : m\left( i\right) ≤ m\left( r\right) }\right)$

holds prior to q's decrementation . To that purpose, smoothsort maintains a further invariant concerning the sequence $m\left( {i : X ≤ s < r}\right)$ of length $q$ :

Pi: the sequence $m\left( {i : X ≤ i ≤ r}\right)$ is a (so-called) standard concatenation of (so-called) stretches.

A "stretch" is a subsequence (of consecutive elements $m$ (i): $h ≤ i < h_1$ ) for some $h < h_1$ ) of a special kind with, when "trusty", the property that none of its elements exceeds its last element, which is called its "root". The maximum of $m$ (i: Xsisr) is thus the maximum stretch root of the standard concatenation for $m$ (i: Xsisr), and relation $P_{1}$ is helpful for establishing $R_{1}$ when the number of stretches that together constitute the sequence $m$ (i: Xsisr) is relatively small.

Stretches, however, don't come in all possible lengths and, when $g$ is not a stretch length, we need more stretches to cover $m(i: X ≤ i ≤ r)$ . The available stretch lengths are the so-called Leonardo numbers

\ldots 2 5 1 5 9 5 3 1 1 (- 1)

given by ${L}{0} = {L}{1} = 1$ and ${L}{n + 2} = {L}{n + 1} + {L}_{n} + 1$ .

given length consists of the largest possible stretch, followed by the standard concatenation of the remainder.

For the sake of the recurrent stretch length computations, we introduce for each stretch length b its "companion" c , i.e. we maintain

(E _ {n}: b = L _ {n} ∧ c = L _ {n - 1})

this is achieved by only modifying variables $b$ and $c$ using "wp" and "down", defined by

up: $b,c \mathrel{\text{:=}} b + c + 1,b $ and $ \operatorname{down}\colon b,c \mathrel{\text{:=}} c,b - c - 1$

The stretches that form a standard concatenation are given by a triple $p, b, c$ , where the $1's$ in the binary representation of $p$ correspond to stretches that do occur in this standard concatenation, with the units position of $p$ corresponding to the stretch of length $b$ with companion $c$ . More precisely, the length of the standard concatenation given by the triple $p, b, c$ can be computed by

\begin{array}{l} l e n g t h := 0 \ ; \frac {d o}{p} p > 0 ∧ e v e n (p) \rightarrow p := p / 2; u p \ I p > 0 ∧ o d d (p) \rightarrow l e n g t h := l e n g t h + b \ ; p := (p - 1) / 2; u p \ \end{array}

od

The above coding of a standard concatenation is possi- sible because ,with the exception of stretch length 1 , which may occur twice in a standard concatenation -e.g. of length 2 or 7-, each stretch length occurs at most once,whereas for stretch length 1 we have $L_{1}$ and $L_{0}$ at our disposal. We adopt the additional convention of recording a single stretch of length 1 in p as $L_{1}$ . We furthermore observe that in p only the two least significant 1's may be adjacent.

We now add to our program

${P}_{2}$ : the length of the standard concatenation re- presented by the triple $p,b,c$ equals $q$ .

\begin{array}{l} \llbracket q, r, p, b, c: \mathrm {i n t}; q, r := 1, X; p, b, c := 1, 1, 1 \ ; \underline {{d o}} g ≠ N \ \rightarrow \mathrm {i f} p \mod 8 = 3 \ \rightarrow p := (p - 1) / 2; u p; p := (p - 1) / 2; u p; p := p + 1 {b ≥ 3 } \ \begin{array}{l}\square p \mod 4 = 1 \rightarrow d o w n; p := 2 \cdot p\end{array} \ ; \underline {{d o}} b ≠ 1 \rightarrow d o w n; p := 2 \cdot p \underline {{o d}}; p := p + 1 {b = 1 } \ \begin{array}{l} \frac {p _ {i}}{t}; q, r := q + 1, r + 1 \end{array} \ \end{array}

\begin{array}{l} \begin{array}{l}\frac {\mathrm {o d}}{\mathrm {d o}} q ≠ 1 \rightarrow q, r := q - 1, r - 1\end{array} \ i f b = 1 \rightarrow p := p - 1 \ ; \underline {{\underline {{d o e v e n}}}} (p) \rightarrow p := p / 2; \underline {{u p o d}} {p \underline {{m o d}} 4 = 1 } \ ] b ≥ 3 \rightarrow p := p - 1 \ f: ; d o w n; p := 2 \cdot p + 1; d o w n; p := 2 \cdot p + 1 {p \mod 8 = 3 } \ \end{array}

| \frac {d}{d t}

Note 1. For the (nonempty!) standard concatenations we have chosen in the above the "normalized" representation with odd(p). (End of Note 1.)

Note 2. The assertions at the end of each alternative have been given in order to stress that -as it should be!- the one repeatable statement is the inverse of the other: the assertions in the one reappear as guards in the other [2]. (End of Note 2.)

At last the time has come to describe how stretches and the standard concatenation define which order relations between elements of $m$ are maintained by smoothsort. We begin with the stretches, of which we shall encounter two types: "trusty stretches" and "dubious stretches".

Denoting a sequence of length ${L}{n}$ by $\left\langle {\operatorname{seq}}{n}\right\rangle$ , we parse for $n ≥ 2$

< s e q _ {n} > = < s e q _ {n - 1} > < s e q _ {n - 2} > < r _ {n} >

where $\langle r_n \rangle$ stands for a singleton sequence. For $\langle \operatorname{seq}n \rangle$ to be a dubious stretch it is required that both $\langle \operatorname{seq}{n-1} \rangle$ and $\langle \operatorname{seq}_{n-2} \rangle$ are trully stretches. For $\langle \operatorname{seq}_n \rangle$ to be a trully stretch it is in addition required that no element of

<seq> exceeds its root ${r}_{n}$ . A stretch of length 1 is by definition trully.

In other words, we may view a stretch as the postorder traversal of a rooted binary tree and it is trusty when no son exceeds its father. It is dubious when no son, except possibly sons of the root, exceeds its father. A dubious stretch is made into a trusty one by applying the operation "sift". -a direct inheritance from heapsort - to its root, where sift is defined as follows: sift applied to an element without larger sons is a skip, sift applied to an element $m(r1)$ that is exceeded by its largest son $m(r2)$ consists of a swap of these two values, followed by an application of sift to $m(r2)$ .

During the second repetition smoothsort maintains

P3: the stretches of the standard concatenation for $m\left( {i : X ≤ r}\right)$ are all trusty

During the first one it mainains the weaker

${P}_{3} :$ of the standard concatenation For $m\left( {i : X\text{is}r}\right)$ the last stretch is dubious ; its other stretches are all trully .

So much for the order relations captured by the

stretches. In addition, smoothsort maintains during the second repetition

${PA} :$ the roots of the stretches of the standard con- catenation are ascending ,

a relation which is useful since $\left( {{P}{3} ∧ {P}{4}}\right) ⇒ {R}_{1}$ . During the first repetition smoothsort maincains the weaker

${P}_{4}{}^{\prime } :$ the roots of the trusty stretches of the standard concatenation that are also stretches of the standard concatenation of length $N$ are ascending.

We now have to investigate

1) what to add to the first repetition for the maintenance 2) what to insert between the two repetitions in order 3) what to add to the second repetition for the main-

Investigation 1. In the case $\mathrm{pmod{8}} = 3$ the standard concatenation ends on a dubious stretch of length b which must be made trusty before it can be combined with the preceding stretch and the following element into a new dubious last stretch. This can be achieved by applying sift to $m(r)$ . Since no

new trusly stretch is added to the standard concatenation, $\mathbb{P}4^{\prime}$ is maintained without further measures. In the case $p \mod 4 = 1$ the standard concatenation ends on a dubious stretch of length $b$ which in this step remains in the standard concatenation; in view of the extension, however, it must be made trusy. In the case $q + c < N$ it suffices to apply sift to $m(r)$ as before. In the case $q + c ≥ N$ , however, just applying sift to $m(r)$ would violate $P4^{\prime}$ , since this stretch of length $b$ also occurs in the standard concatenation of length $N$ . Making a dubious stretch trusy and including its root in the sequence of ascending roots is achieved by applying "frinkle" to $m(r)$ . (As we will see later, trinkle is like sift, but for a partly ternary tree.) (End of Investigation 1.)

Investigation 2. It suffices to apply trinkle to $m\left( r\right)$ . (End of Investigation 2.)

Investigation 3. In the case $b = 1$ the standard concatenation loses its last stretch, and $P_{3} \wedge P_{4}$ remains invariant without additional measures. In the case $b ≥ 3$ , the last stretch is replaced by two trushy ones. Hence $P_{3}$ is maintained. To restore $P_{4}$ it would suffice to apply trinkle first to the root of the first new stretch and then to the root of the second new stretch, but this would fail to exploit the fact that the new stretches are already trushy to start

with. This is exploited by applying "pretrinkle" in order to those roots. (End of Investigation 3.)

In order to enable the reader to check the code in which the calls on sift, trinkle, and pretrinkle have been inserted, we give the calling conventions.

Routine sift is applied to the root $m(r)$ of a stretch of length $b_1$ , of which $c_1$ is the companion. Routine trinkle is applied to the root $m(r)$ of the last stretch of the standard concatenation represented by the triple $p, b, c$ ; this representation need not be normalized. Routine pretrinkle is applied to root $m(r)$ of a stretch of length $c$ which is preceded by the nonempty standard concatenation represented by the triple $p, b, c$ ; again this representation is not necessarily normalized.

Note that $p \coloneqq \left( {p - 1}\right) /2;p \coloneqq \left( {p - 1}\right) /2;p \coloneqq p + 1$ " reduces to " $p \mathrel{\text{:=}} \left( {p + 1}\right) /4$ " and that " $r \mathrel{\text{:=}} r - b + c$ ; down; $r \mathrel{\text{:=}} r + c$ " decreases r by 1 .

smoothesort: 11 $q,r,p,b,c,r1,b1,c1:int$ $9, r:= 1,X; p, b, c:= 1,1,1$ $\underline{\underline{\mathsf{d}}}\circ q≠ N$ $\rightarrow \mathbf{r}1\coloneqq \mathbf{r}$ $\begin{array}{l}\text{if}p\bmod 8 = 3\ \rightarrow b1,c1:= b,c;sift; p := (p + 1)/4; up; up\ \text{I}p\bmod 4 = 1\ \rightarrow ifq + c < N\rightarrow b1,c1:= b,c;sift\ \text{I}q + c≥ N\rightarrow trinkle}\ \underline{\underline{\mathsf{f}}}i;\operatorname {down};p:= 2\cdot p\ \text{;}do b≠ 1\rightarrow down;p:= 2\cdot p\underline{\underline{\mathsf{o}}}d; p:= p + 1\ \underline{\underline{\mathsf{f}}}i;q,r:= q + 1,r + 1\ \underline{\underline{\mathsf{o}}}d;r;r;trinkle \end{array}$ $\begin{array}{rl} & {\mathrm{~o~d~};\mathrm{~r~1~}:= \mathrm{~r};\mathrm{~t~r~i~n~k~l~e}}\ & {\mathrm{~;~d~o~}q≠ 1}\ & {\rightarrow q:= q - 1}\ & {\mathrm{;~i~f}b = 1}\ & {\rightarrow r:= r - 1;p:= p - 1;\mathrm{~d~o~e~v~en}(p)\rightarrow p:= p / 2;up\underline{\underline{\mathsf{o}}}d}\ & {\mathrm{~I~}b≥ 3}\ & {\rightarrow p:= p - 1;r:= r - b + c;}\ & {\mathrm{;~i~f}p = 0\rightarrow skip[]p > 0\rightarrow pretrinkle f_i}\ & {\mathrm{;~dow n};p:= 2.p + 1;r:= r + c;pretrinkle}\ & {\mathrm{;~dow n};p:= 2.p + 1}\ & {\mathrm{f_i}} \end{array}$

\begin{array}{l} u p 1: b 1, c 1 := b 1 + c 1 + 1, b 1 \ d o w n 1: b 1, c 1 := c 1, b 1 - c 1 - 1 \ s i f t: \ \mathrm {d o} b 1 ≥ 3 \rightarrow \ \llbracket r 2: i n t; r 2 := r 1 - b 1 + c 1 \ \begin{array}{r l}&{\mathrm {i f} m (r 2) ≥ m (r 1 - 1) \rightarrow s k i p}\&{\mathrm {I I} m (r 2) ≤ m (r 1 - 1) \rightarrow r 2 := r 1 - 1; d o w n 1}\end{array} \ \begin{array}{r l}&{\frac {f _ {i}}{p} m (r 1) ≥ m (r 2) \rightarrow b 1: = 1}\&{\frac {f _ {j}}{q} m (r 1) < m (r 2)}\end{array} \ \rightarrow m: \mathrm {s w a p} (r 1, r 2); r 1 := r 2; \mathrm {d o w n} 1 \ \prod^ {p} \ \overline {{o d}} \ \end{array}

\begin{array}{l} p r e f r i n k l e: \ r 1 := r - c \ ; \mathrm {i f} m (r 1) ≤ m (r) \rightarrow s k i p \ m (r _ {1}) > m (r) \rightarrow m: s w a p (r, r _ {1}); f r i n k l e \ p _ {i} \ \end{array}

Trinkle is very similar to sift when we regard each stretch root as stepson of the root of the next stretch. Applied to a root without larger sons, trinkle is a skip; otherwise the root is swapped with its largest son, etc. The trouble with the code is that all sorts of sons may be missing. In the following, trinkle is eventually reduced to a sift.

frinkle:

\begin{array}{l} \llbracket p _ {1}: \mathrm {i n t}; p _ {1}, b _ {1}, c _ {1} := p, b, c \ ; \underline {{d o}} p 1 > 0 \rightarrow \ \begin{array}{l}{I [ r 3: i n t; \underline {{d o e v e n}} (p 1) \rightarrow p 1 := p 1 / 2; u p 1 \underline {{a d}}; r 3 := r 1 - b 1}\end{array} \ ; i f p 1 = 1 \underline {{c o r}} m (r 3) ≤ m (r 1) \rightarrow p 1 := 0 \ [ [ p _ {1} > 1 \underline {{c a n d}} m (r _ {3}) > m (r _ {1}) \ \rightarrow p _ {1} := p _ {1 - 1} \ ; i f b 1 = 1 \rightarrow m: s w a p (r 1, r 3); r 1 := r 3 \ [ b _ {1} ≥ 3 \rightarrow \ \left[ r 2: i n t; r 2 := r 1 - b 1 + c 1 \right. \ ; i f m (r 2) ≥ m (r 1 - 1) \rightarrow s k i p \ m (r 2) ≤ m (r 1 - 1) \ \rightarrow r 2 := r 1 - 1; d o w n 1; p 1 := 2 \cdot p 1 \ F _ {i} \ ; \mathrm {i f} m (r 3) ≥ m (r 2) \ \rightarrow m: s w a p (r _ {1}, r _ {3}); r _ {1} := r _ {3} \ m (r 3) ≤ m (r 2) \ \rightarrow m: s w a p (r 1, r 2); r 1 := r 2; d o w n 1; p 1 := 0 \ F _ {i} \ \end{array}

${p}_{i}$

${a}{i} \in a {a}{i}$ 的最小值为 $k$ .

d

And this concludes the code, in which I have abstained from implementation dependent optimizations.

In retrospect,

While heapsort prunes the tree leaf by leaf, smoothsort prunes the tree at the root, and immedi- diately one of heapsort's charms is lost: while the tree in heapsort remains beautifully balanced, the tree in smoothsor can get very skew indeed. So why bother about smoothsor at all? Well, I wanted to design a scrting algorithm, in general of order N.log N, that would be of order N when the array is initially sorted.

This is also the answer to the question why I introduced $P_4$ . By dropping $P_4$ one can disperse with trinkle and the code becomes much simpler. The price to be paid is a search for the maximum stretch root in order to establish $R_1$ . Though such a sorting algorithm is quite defensible, I rejected the option because it is never of the order $N$ .

One can also raise the question why I have chosen the Leonardo numbers for my stretch lengths: ... 63 31 15 7 3 1 is also a possiblity, which seems attractive since each stretch can now be viewed as the postorder traversal of a completely balanced tree. I know why I chose the Leonardo numbers : with the balanced binary trees the average number of stretches

is $1.2559\left( { = \frac{1}{4} \cdot \left( {5 + {V}{5}}\right) \cdot \left( {{2}^{\log }\left( {1 + {V}{5}}\right) - 1}\right) }\right)$ times the average number of stretches with the Leonardo numbers. (I do not present this ratio as a com- pelling argument.)

It is possible that others have thought of this algorithm but have rejected it for valid reasons, as yet unknown to me. It is not mentioned in [3], a recent article that compares five well-known sorting algorithms when fed with initially nearly sorted sequences. (It compares Straight Insertion Sort, Shellsort, Straight Merge Sort, Quickersort, and Heapsort.)

Besides the possible interest in smoothsort I had another reason for developing it to the degree I did and for writing the above. (It took me three weeks, but I consider them well-spent.) The reason was that I knew beforehand that in trying to present smoothsort in an intelligible manner I would encounter considerable difficulties. I hope they have been surmounted sufficiently well.

Acknowledgements

I am greatly indebted to C.S. Scholten and to all the members of the Tuesday Afternoon Club, with whom I had the privilege of discussing the algorithm, its coding, and its presentation. They

have helped me clarifying my own thoughts and have suggested several significant simplifications.

References.

[0] Williams, J.W.J. Algorithm 232 HEAPSORT C.A.C.M., 7,6 (June 1964), pp. 347-348 [1] Floyd, Robert W., Algorithm 242 TREESORT 3. C.A.C.M., 7,12 (Dec. 1964), p. 701 [2] Bauer, F.L. and Broy, M. (Ed.), Program Construction, Lecture Notes in Computer Science 69, Berlin, Heidelberg, New York, Springer Verlag, 1979, pp. 54-57 [3] Cook, Curtis R. and Kim, Do Jin, Best Sorting Algorithm for Nearly Sorted Lists, C.A.C.M., 23,11 (Nov. 1980) pp.620-624

Plataanstraat 5 5671 AL NUENEN The Netherlands

12 July 1981 prof. dr. Edsger W. Dyrksha Burroughs Research Fellow