A minor improvement of Heapsort

E W D 7 8 9 b - o

A minor improvement of Heapsort.

Heapsort is an efficient algorithm for sorting in situ the elements of a linear array $m$ (i: osiC $N$ ). When sorting the elements in ascending order, the algorithm maintains $H2$ , defined by

${H}{2} : \left( {\underline{A}{i,j} : p ≤ i < j < q ∧ {C}{2}\left( {i,j}\right) : m\left( i\right) ≥ m\left( j\right) }\right)$

where $C2$ is given by

C _ {2} (i, j): 2 \cdot i < j ≤ 2 \cdot (i + 1)

Note that in terms of CC2, i.e. the transitive closure

C C _ {2} (i, j): C _ {2} (i, j) \vee (\underline {{E}} k: C _ {2} (i, k): C C _ {2} (k, j))

we could have formulated also

${H}{2} : \left( {\underline{\mathrm{A}}{i,j} : p ≤ i < j < q ∧ C{C}{2}\left( {i,j}\right) : m\left( i\right) ≥ m\left( j\right) }\right)$

Relation H2 enjoys the useful property

(H _ {2} ∧ p = 0) ⇒ (\underline {{A}} j: 0 ≤ j < q: m (0) ≥ m (j)) . (0)

Algorithm Heapsort has the following form:

\begin{array}{l} p, q := N \mathrm {d i v} 2, N; {H _ {2} \wedge q = N } \ \frac {d o}{d t} p ≠ 0 \rightarrow p := p - 1; \ {H _ {2} (p: = p + 1) } s i f t {H _ {2} \wedge q = N } \ \underline {{o d}}; {H _ {2} \wedge p = 0 \wedge q = N } \ \begin{array}{r l}{\underline {{d o}} q > 1 \rightarrow \left{H _ {2} \wedge p = 0 \right} q := q - 1; m: s w a p (0, q);}\{\left{H _ {2} (p := p + 1) \right} s i f t \left{H _ {2} \wedge p = 0 \right}}\end{array} \ \end{array}

Oo

Here " $H_{2}\left(p = p + 1\right)$ " stands for the predicate that is derived from $H_{2}$ by replacing in it all (free) occurrences of $p$ by $p + 1$ . Since $q = N$ is a precondition of the second repetition and the latter maintains $p = 0$ , properly (0) ensures that the sorted sequence is built up "from right to left".

By rearranging elements of array m, routine

{H _ {2} (p := p + 1) } \mathrm {s i f} {H _ {2} }

it does so by establishing $- {by} w \mathrel{\text{:=}} p -$ and main-

S H _ {2}: (\underline {{A}} i, j: p ≤ i < j < q ∧ C C _ {2} (i, j): m (i) ≥ m (j) \lor i = w),

which enjoys the useful property

(S H _ {2} ∧ 2. w + 1) ≥ q) ⇒ H _ {2}.

Routine sift can repeatedly perform under invariance of ${SH2}$ either $w \mathrel{\text{:=}} 2 \cdot w + 1$ or $w \mathrel{\text{:=}} 2 \cdot w + 2$ ;

We can do better by replacing ${C2}$ by ${C3}$ ,

C _ {3} (i, j): 3 \cdot i < j ≤ 3 \cdot (i + 1)

(and, similarly, CC2, H2, and SH2 by CC3,H3, and SH3 respectively). Firstly, we can then start with a smaller $p$ ,viz. $\left( {N + 1}\right)$ div 3; secondly,sift con then "triple" w at the cost of 3 comparisons and 1 swap in array m . Thus 6 comparisons and 2 swaps multiply w by 9 , whereas originally 6 comparisons and 3 swaps were needed for a factor of 8 . (With the analogous ${C}_{4}$ ,etc.,the gain in comparisons is lost again : ${2}^{3} < {3}^{2}$ ,but ${2}^{4} = {4}^{2}$ . Since ${2}^{5} > {5}^{2}$ , ${C5}$ eK. is expected to lead to more comparisons in sif.)

A worst-case sif $f$ is one that terminates with $2 \cdot w + 1 ≥ q$ (or $3 \cdot w + 1 ≥ q$ respectively). A sort in which all sifts are worst-case sifts would clearly

be a worst-case sort. Since such sorts can occur -see below- and our modification improves worst-case

The crucial observation is that, when upon comple- tion of a call of sift the final value of w is not destroyed, the effect of that call can be undone: sift itself has a unique inverse $\operatorname{sift} - 1$ (ending with $w = p$ ). Starting with an increasing array $m$ ,we can play Heapsort backwards,supplying each time $\operatorname{sift} - 1$ with a proper initial value for $w$ such that $2 \cdot w + 1 ≥ q$ (or $3 \cdot w + 1 ≥ q$ respectively)-for a detailed discussion of the notion "proper", see below-. Our backwards game ends with an $m$ that would lead to a sort with worst-case shifts only.

Now a detailing of the notion "proper". Our back. wards game starts increasing q repeatedly by

\begin{array}{l} {H _ {2} \wedge p = 0 } \mathrm {s i f t} ^ {- 1} {H _ {2} (p := p + 1) }; \ m: \operatorname {s w a p} (0, q); q := q + 1 {H _ {2} \wedge p = 0 } (1) \ \end{array}

Independently of our choice of $W$ , ${H2}$ holds after the swap because the new $m\left( 0\right)$ satisfies (A): $0 ≤ j < q : m\left( 0\right) ≥ m\left( j\right)$ ). But does ${H2}$ hold after $q = q + 1$ ? If does if $m\left( {q - 1}\right)$ is then small enough. We can achieve this,for instance,by choosing for ${sif}^{-1}$ initially $w = q - 1$ ; program section (1) then

maintains

(\underline {{A}} i: 0 ≤ i < q: m (i) ≥ m (q - 1))

Our backwards game continues increasing $p$ repreh- edly by

{H _ {2} \wedge q = N } \mathrm {s i f f} ^ {- 1} {H _ {2} (p := p + 1) };

p := p + 1

Since $p = 0$ is now not an invariant, we must take precautions to ensure that $\mathrm{sift}^{-1}$ can end with $w = p$ ; here "proper" means that for $\mathrm{sift}^{-1}$ we choose initially a $w$ satisfying $CC2(p, w)$ , i.e., such that $\underline{d} ≠ p \rightarrow w := (w - 1) \underline{d} \vee 2$ and terminates. For $C3$ , etc., the same argument applies.

Compared to the above worst-case analysis, the analysis of the average case seems too difficult and insufficiently rewarding.

Acknowledgements. I am indebted to Ross A. Homsberger, who sent me a collection of combinatorial problems, one of which was solved by observing $2^{3} < 3^{2}$ . (The problem was how to partition a given positive integer into positive integer parts such that the product of the parts is maximal. The solution is to take as many parts $= 3$ as is possible without introducing a remaining part $= 1$ . The preponderance of 3's is not amazing: 3 is the nearest integer

approximation of e.) I am indebted to R.W. Bulterman, who spotted an error in my original form of H3 which failed to satisfy the analogue of (0); in the literature, Heapsort traditionally sorts m (i: 15 is N) and unthinkingly I had adopted that unfortunate convention, which induced my error. I have gratefully adopted Gary Marc Levin's suggestion to indicate subscript ranges uniformly by a predicate. Finally I am indebted to Eric C.R. Hehner and the members of the Tuesday Afternoon Club, who helped me with the worst-case analysis, in which we clearly benefitted from our earlier work on program inversion (see [1]).

[0] Wirth, Niklans, Algorithms + Data Structures = Programs, Englewood Cliffs, NJ, USA, Prentice-Hall Inc., 1976, pp. 72-76

[1] Bauer, F.L. and Brog, M. (Ed.), Program Construction, Lecture Notes in Computer Science 69, Berlin Heidelberg New York, Springer Verlag, 1979, pp. 54-57

P.S. Today, 26 May 1981, I learned that Les Goldschlager of Wollongong University, Australia, came to the same con- clusion while working at Toronto, Canada. (End of P.S.)

Plataanstraat 5 5671 AL NUENEN The Netherlands

24 May 1981 prof. dr. Edsger W. Dgkesra Burroughs Research Fellow