Editing Smoothsort (section)

==Operations==
While the two phases of the sorting procedure are opposite to each other as far as the evolution of the sequence-of-heaps structure is concerned, they are implemented using one core primitive, equivalent to the 
"sift down" operation in a binary max-heap.

===Sifting down===
The core sift-down operation (which Dijkstra calls "[[wikt:trinkle|trinkle]]") restores the heap invariant when it is possibly violated only at the root node.  If the root node is less than any of its children, it is swapped with its greatest child and the process repeated with the root node in its new subtree.

The difference between smoothsort and a binary max-heap is that the root of each stretch must be ordered with respect to a third "stepson": the root of the preceding stretch.  So the sift-down procedure starts with a series of four-way comparisons (the root node and three children) until the stepson is not the maximal element, then a series of three-way comparisons (the root plus two children) until the root node finds its final home and the invariants are re-established.

Each tree is a [[Binary tree#Types of binary trees|full binary tree]]: each node has two children or none. There is no need to deal with the special case of one child which occurs in a standard implicit [[binary heap]].  (But the special case of stepson links more than makes up for this saving.)

Because there are {{math|''O''(log&nbsp;''n'')}} stretches, each of which is a tree of depth {{math|''O''(log&nbsp;''n'')}}, the time to perform each sifting-down operation is bounded by {{math|''O''(log&nbsp;''n'')}}.

===Growing the heap region by incorporating an element to the right===
When an additional element is considered for incorporation into the sequence of stretches (list of disjoint heap structures) it either forms a new one-element stretch, or it combines the two rightmost stretches by becoming the parent of both their roots and forming a new stretch that replaces the two in the sequence. Which of the two happens depends only on the sizes of the stretches currently present (and ultimately only on the index of the element added); Dijkstra stipulated that stretches are combined if and only if their sizes are {{math|''L''(''k''+1)}} and {{math|''L''(''k'')}} for some {{mvar|k}}, i.e., consecutive Leonardo numbers; the new stretch will have size {{math|''L''(''k''+2)}}.

In either case, the new element must be sifted down to its correct place in the heap structure.  Even if the new node is a one-element stretch, it must still be sorted relative to the preceding stretch's root.

====Optimization====
Dijkstra's algorithm saves work by observing that the full heap invariant is required at the end of the growing phase, but it is not required at every intermediate step.  In particular, the requirement that an element be greater than its stepson is only important for the elements which are the final tree roots.

Therefore, when an element is added, compute the position of its future parent.  If this is within the range of remaining values to be sorted, act as if there is no stepson and only sift down within the current tree.

===Shrinking the heap region by separating the rightmost element from it===
During this phase, the form of the sequence of stretches goes through the changes of the growing phase in reverse. No work at all is needed when separating off a leaf node, but for a non-leaf node its two children become roots of new stretches, and need to be moved to their proper place in the sequence of roots of stretches. This can be obtained by applying sift-down twice: first for the left child, and then for the right child (whose stepson was the left child).

Because half of all nodes in a full binary tree are leaves, this performs an average of one sift-down operation per node.

====Optimization====
It is already known that the newly exposed roots are correctly ordered with respect to their normal children; it is only the ordering relative to their stepsons which is in question.  Therefore, while shrinking the heap, the first step of sifting down can be simplified to a single comparison with the stepson.  If a swap occurs, subsequent steps must do the full four-way comparison.