Unifying Seemingly Disparate Sorting Algorithms
In their joint report `An introductory essay on three algorithms for sorting in situ', Van Gasteren and Dijkstra explain what Insertion Sort, Heap Sort, and Smooth Sort have in common and how one can derive one sorting algorithm from the other.
Insertion Sort can be explained in terms of a descending chain in the following manner. During each iteration of Insertion Sort for a list of N elements, the descending chain grows with one new element: the descending chain of length n and a new element are transformed into a new descending chain of length n+1. At the end of the day, the descending chain represents the sorted list of N elements. Insertion Sort thus depends on a growing descending chain which is initially of size 0 and finally of size N.
By generalizing the notion of a chain into a tree, Van Gasteren and Dijkstra continue by describing a family of related sorting algorithms, a family which contains the Heap Sort and Smooth Sort algorithms as special cases. A chain is, after all, a tree of a special form.
An attractive generalization of a chain is a rooted tree. Analogously [to a descending chain], a descending tree is one in which each element dominates its entire offspring. [p.4, my emphasis]
It should be stressed, however, that the descending tree in Heap Sort or Smooth Sort serves another purpose than the descending chain in Insertion Sort. During each iteration of Insertion Sort, the descending chain grows with one element. During each iteration of Heap Sort or Smooth Sort, the descending tree shrinks with one element. In the case of Insertion Sort, the descending chain represents the sorted part of the list. In the case of Heap Sort or Smooth Sort, the descending tree represents the part of the list that has not been sorted.
During each iteration in Heap Sort or Smooth Sort, the descending tree of size n+1 splits into its root r, on the one hand, and a new descending tree of size n, on the other hand. The root r adjoins the already sorted list of elements, a list that grows by one element in each iteration. To obtain the new descending tree of size n from all the offspring of root r, some appropriate reshuffling is needed. This reshuffling can be implemented in terms of a growing descending tree, which is initially of size 0 and finally of size n. To accomplish that, one has to judiciously choose a path in the growing descending tree (of final size n) and apply the same ideas underlying the growing descending chain of Insertion Sort. Here, thus, lies a strong similarity between all three sorting algorithms.
Finally, I mention that Heap Sort and Smooth Sort differ in how the reshuffling is implemented. For further details, see [AvG16/EWD809].