A minor improvement of Heapsort

A minor improvement of Heapsort.

Heapsort is an efficient algorithm for sorting in situ the elements of a linear array $M(i: o ≤ i < N)$ . When sorting the elements in ascending order, the algorithm maintains $H(p)$ , defined by

H (p): (\underline {{A}} i, j: p ≤ i < j < q ∧ 2. i < j ≤ 2. (i + 1): M (i) ≥ M (j))

which enjoys the useful property

H (0) ⇒ (\underline {{A}} _ {j}: 0 < j < q: M (0) ≥ M (j)) (0)

The algorithm has the following form:

\begin{array}{l} p, q := N \mathrm {d i v} 2, N; {H (p) } \ \underline {{d o}} p ≠ 0 \rightarrow p := p - 1; {H (p + 1) } s i f {H (p) } \underline {{o d}}; \ \underline {{d o}} q > 1 \rightarrow {H ^ {\prime} (0) } q := q - 1; M: s w a p (0, q); \ {H (p + 1) } s i f t {H (p) } \ \end{array}

ad

Since $p = 0$ is a further invariant of the second repetition, property (o) ensures that the sorted sequence is built up "from right to left."

The routine $\mathit{sift}$ establishes -by $w \coloneqq p - a n d$ maintains ${sH}$ ,defined by

SH: (A) $j : p ≤ i < j < q ∧ {2.4} < j ≤ 2\left( {i + 1}\right) : M\left( i\right) ≥ M\left( j\right) v i = w} ,$

which enjoys the useful property

S H ∧ 2 \cdot w + 1 ≥ q ⇒ H (p)

Routine sif1 can repeatedly perform under invariance of SH either $w \mathrel{\text{:=}} 2 \cdot w + 1$ or $w \mathrel{\text{:=}} 2 \cdot w + 2$ ; sift com. Pares each time $M\left( w\right)$ with the maximum of $M\left( {2 \cdot w + 1}\right)$ and $M\left( {2 \cdot w + 2}\right)$ . If $M\left( w\right)$ is large enough, $H\left( p\right)$ holds and sift terminates; other- wise $W$ can be "doubled" at the price of 2 com- parisons and 1 swap in array $M$ . For further details we refer the reader to [0].

We can do better (in terms of numbers of com- parisons and swaps needed) by replacing $H\left( p\right)$ by ${H}_{3}\left( p\right) -$ and,similarly, ${SH}$ by ${SH3} -$

H _ {3} (p): (\underline {{A}} i, j: p ≤ i < j < q ∧ 3. i < j ≤ 3. (i + 1): M (i) ≥ M (j)).

Firstly, we can then start with a smaller $p$ , viz. (N+1) div 3; secondly, sift can then "triple" w at the cost of 3 comparisons and 1 swap in array M. Thus 6 comparisons and 2 swaps multi- phy w by 9 , whereas originally 6 comparisons and 3 swaps were needed for a factor of 8 . (With the analogous H4(p), the gain in comparisons needed is lost again : $2^{3} < 3^{2}$ , but $2^{4} = 4^{2}$ . Since $2^{5} > 5^{2}$ , H5(p) is expected to lead to more comparisons in sift.)

A worst-case sift 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 com- plection of a call of sift the final value of w is not destroyed, the effect of that call can be undone: sift it self has a unique inverse $s i f t^{-1}$ (ending with $w = p$ ). Starting with an increasing array M, we can play Heapsort backwards, supplying each time.

Now a detailing of the notion "proper". Our backwards game starts increasing 9 repeatedly

{H (p) } \mathrm {s i f} 7 ^ {- 1} {H (p + 1) };

M: s w a p (q, 0); q := q + 1 {H (0) } \tag {2}

Independently of our choice of $w$ , $H\left( 0\right)$ holds after the swap, because the new $M\left( 0\right)$ satisfies (A) $j : 0 ≤ j < q : M\left( 0\right) ≥ M\left( j\right)$ ). But does $H\left( 0\right)$ hold after

$q = q + 1?$ It does if $M\left( {q - 1}\right)$ is then small enough. We can achieve this,for instance,by initializing for sif ${f}^{-1}$ $w = q - 1$ ; program section (2) then mainains (A i: p < i < q: M(i) ≥ M(q - 1)). Our backwards game continues increasing p repeated by ${ H\left( p\right) }$ sift ${}^{-1}{ H\left( {p + 1}\right) } ;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 the initial value of $w$ is such that $\underline{\mathrm{do}} w ≠ p \rightarrow w := (w - 1) \underline{\mathrm{div}} 2$ or $\underline{\mathrm{do}} w ≠ p \rightarrow w := (w - 1) \underline{\mathrm{div}} 3$ terminates.

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 series of combina- torial problems, one of which used $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 also indebted to R.W. Bultherman, who spotted an error in my original form of H3(p), 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 was responsible for my error. 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, Niklaus, Algorithms + Data Structures = Programs, Englewood Cliffs, NJ, USA, Prentice-Hall Inc., 1976, pp. 72-76

[1] 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.

Plataonsstraat 5 5671 AL NUENEN The Netherlands

14 May 1981 prof. dr. Edsger W. Dgksta Burroughs Research Fellow.