Editing Smoothsort (section)

===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.