Editing Smoothsort (section)

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