Page "Smoothsort" Paragraph 8

The algorithm is simple.

We start by dividing up our unsorted array into a single heap of one element, followed by an unsorted portion.

A one-element array is trivially a valid sequence of heaps.

This sequence is then grown by adding one element at a time to the right, performing swaps to keep the sequence property and the heap property, until it fills the entire original array.