An alternative to heapsort for sorting in situ

An alternative to Heapsort for sorting in situ.

I am getting a bit tired of sorting algorithms because, since I happen to look at them, I get the impression that their number is unbounded. It is therefore with great hesitation that I record having discovered a next class of them.

An often quoted disadvantage of Heapsort -whether this disadvantage is serious or not is none of my concerns- is that it absolutely fails to exploit the circumstance that the sequence is initially "almost sorted." While sharing the $N \cdot \log N$ characteristic with Heapsort, the alternative does not share with Heapsort. This disadvantage - it is, however, of greater clerical complexity-: in the extreme case that the sequence is initially sorted, no rearrangement whatsoever takes place.

For the sake of brevily I shall consider sorting the integer array $m(i : 0 ≤ i ≤ N)$ in ascending order. For integer $p$ the following two relations are of interest.

${P}{0} : \left( {\underline{A}{i}{,j} : 0 ≤ i < p A i ≤ j < N}\right) : m\left( i\right) ≤ m\left( j\right)$

It expresses that the first $p$ elements of $m$ have their final value; initialization is possible since $\left( {p = 0}\right) ⇒ {P}_{0}$ and we are done when $P \cap p = N - 1.$

Relation ${P}_{1}$ is,in addition,about a rooted tree of which the elements $m\left( {i : p ≤ i < N}\right)$ are the vertices.

${P}_{1}$ : in free $t$ ,no element exceeds any of its successors in $t$ ,and pre-order traversal of $t$ visits the elements of $m\left( {i : p ≤ i < N}\right)$ in the order of increasing index.

(In the pre-order traversal the root of any subtree precedes all other vertices of that subtree, and the successors of a vertex are ordered.)

From ${P}{1}$ we conclude, firstly that the root is the minimum of $m\left( {i : p ≤ i < N}\right)$ and, secondly, that $m\left( p\right)$ is the root. Hence $m\left( p\right) =$ minimum of $m\left( {i : p ≤ i < N}\right) .{If}$ ,in addition, $m\left( p\right)$ has (at most) 1 successor, $p \mathrel{\text{:=}} p + 1$ mainains $P ∧ {P}{1}$

The structure of the sorting algorithm is

choose and rearrange $m\left( {i : \operatorname{OSS} < N}\right)$ such as to establish $P{0.1}{P}_{1}$ for $p = {0}^{ * }$ ;

do $p ≠ N - 1 \rightarrow$ rearrange $m(i: p ≤ i < N)$ and modify $t$ under invariance of $\mathbf{P}0 \wedge \mathbf{P}1$ such that $m(p)$ has a single successor $i$ ; $p := p + 1$

od

Initially we choose t reasonably well-balanced. (It need not be a binary tree; I am now not inter-ested in its optimal shape.) Like in Heapsort, the first phase can be done by

\begin{array}{l} p := N - 1; \ \underline {{d o}} p ≠ 0 \rightarrow p := p - 1; s i f (p) \underline {{o d}} {P _ {0} \wedge P _ {1} \wedge p = 0 }. \ \end{array}

Let the root have more than one successor. Let $m(v)$ be its last successor and $m(w)$ its last successor but one. We can reduce the number of successors of the root by (changing t and) making $m(v)$ the last successor of $m(w)$ ; this rearrangement does not violate the pre-order traversal of $t$ and a subsequent call of $\operatorname{sift}(w)$ restores $P_1$ .

It is the administration of t that makes this algorithm clerically awkward. The possible values (= shapes) of t are fully determined by its initial value to . In t each node has at most one "sin- gular successor", i.e. a successor it did not have m to . A singular successor is always a last successor, and the potential singular successor of any node is uniquely determined by to .

In to, the potential singular successor of a vertex v is given recursively as follows if v has no predecessor (i.e. is the root) its potential singular successor is void,

if $v$ is the last successor of its predecessor, its potential singular successor is the po-. tential singular successor of its predecessor. if $v$ is not the last successor of its predecessor, its potential successor is the next successor of its predecessor.

If we choose, with $K$ the minimal value such that $2^{K} > N$ , for to the completely balanced tree for $2^{K - 1}$ elements, determining the regular successors of a vertex is no problem provided its level is known. Since the total number of singular successors is bounded by $K$ , there is a fair chance that, at the expense of a modest amount of additional storage, the scheme can be implemented quite efficiently.

Plataansstrat5 5671 AL NUENEN The Netherlands

19 June 1981 prof. dr. Edsger W. Dgiksha Burroughs Research Fellow

P.S. For the above class of sorting algorithms I have invented the name "smoothsort", for what is a sorting algorithm without a name?

EWD.