A minor improvement of Heapsort

A minor improvement of Heapsort.

Heapsort is a very efficient algorithm for sorting the elements $M(i)$ for $1 ≤ i < N$ of a linear array. To sort the elements in ascending order the algorithm maintains $H(p,q)$ defined by

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

which enjoys the useful property

H (p, q) ∧ p = 1 ⇒ (\exists j: 1 ≤ j < q: M (1) ≥ M (j)) . (0)

The algorithm has the following form:

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

[\text{ad.}]

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

The routine sif $t$ establishes $- b\left( {w = p - a}\right)$ and mainains ${SH} : \left( {A,i,j : p ≤ i < j < q,2 \cdot i ≤ j < 2.}\right) \left( {i + 1}\right) : M\left( i\right) ≥ M\left( j\right) V,w = i} ,$

which enjoys the useful property $SH \wedge 2 \cdot w ≥ q ⇒ H(p, q)$ . The routine sift can repeatedly perform under invariance of $SH$ $w := 2 \cdot w$ or $w := 2 \cdot w + 1$ ; sift compares each time $M(w)$ with the maximum of $M(2 \cdot w)$ and $M(2 \cdot w + 1)$ . If $M(w)$ is large enough, $H(p, q)$ holds and sift terminates; otherwise $w$ can be "doubled" at the price of 2 comparisons and 1 swap in array $M$ . For further details we refer the reader to [0].

We can do better by replacing $H\left( {p,q}\right)$ by ${H}_{3}\left( {p,q}\right) -$ and,similarly, ${SH}$ by ${SH3} -$

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

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

Some weeks ago I received under the title "Gleason

From Combinatorics" from Ross A. Honsberger of Waterloo University a short series of combinatorial problems with their solutions. One of them was how to partition a positive integer $n ≥ 2$ into one or more (positive in- teger) parts so that the product of the parts is a maximum. The answer is:

for $n = {3k}$ , use $k = {3}^{1}s$ ; $n = {3k} + 2$ , use $k = {3}^{1}s$ and $a = 2$ $n = {3k} + 4,$ use $k = {3}^{1}s$ and $a = 4$ .

(The prepunderance of 3's is not so amazing: 3 is the best integer approximation of e , which is the solution of the corresponding continuous problem. The observation $2^{3} < 3^{2}$ was part of the justificaiton of the discrete solution.) That the study of a gem from rather pure mathematics led to the discovery how to improve the efficiency of a standard algorithm, which is justly famous for its efficiency, was a very pleasant surprise. I think it is a lesson.

Plataansstraat 5 5671 AL NUENEN The Netherlands

8 May 1981 prof. dr. Edsger W. Dgiksha Burroughs Research Fellow

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