[1] Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n) operations (see big O notation),[2] but it is not a stable sort.
Like heapsort, smoothsort organizes the input into a priority queue and then repeatedly extracts the maximum.
More formally, every position i is the root of a unique subtree, whose nodes occupy a contiguous interval that ends at i.
An initial prefix of the array (including the whole array), might be such an interval corresponding to a subtree, but in general decomposes as a union of a number of successive such subtree intervals, which Dijkstra calls "stretches".
In the first (heap growing) phase of sorting, an increasingly large initial part of the array is reorganized so that the subtree for each of its stretches is a max-heap: the entry at any non-leaf position is at least as large as the entries at the positions that are its children.
Alternatively, if there is a finite bound N on the size of arrays to be sorted, a precomputed table of Leonardo numbers can be stored in O(log N) space.
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.
The core sift-down operation (which Dijkstra calls "trinkle") restores the heap invariant when it is possibly violated only at the root node.
There is no need to deal with the special case of one child which occurs in a standard implicit binary heap.
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.
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.
Therefore, while shrinking the heap, the first step of sifting down can be simplified to a single comparison with the stepson.
Smoothsort takes O(n) time to process a presorted array, O(n log n) in the worst case, and achieves nearly linear performance on many nearly sorted inputs.
[2] The smoothsort algorithm needs to be able to hold in memory the sizes of all of the trees in the Leonardo heap.
[5] Named after the rows of trees of decreasing size often seen in Dutch polders, it performs fewer comparisons than smoothsort for inputs that are not mostly sorted, but cannot achieve linear time for sorted inputs.
Instead, each time the heap is shrunk in the second phase, the roots are searched to find the maximum entry.
The same structure has been proposed as a general-purpose priority queue under the name post-order heap,[6] achieving O(1) amortized insertion time in a structure simpler than an implicit binomial heap.