Editing Smoothsort (section)

===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'')}}.