Summary

Smoothsort is a comparison-based sorting algorithm invented by Edsger Dijkstra. While standard Heapsort builds a single binary heap, Smoothsort maintains a forest of heaps where the size of each tree is a Leonardo number ($L(n)$). The state of this forest is cleverly encoded in a single bitvector (variable p in the code), allowing the algorithm to run in $O(1)$ auxiliary space. Unlike Heapsort, Smoothsort is adaptive: if the input is already sorted, it constructs the heap forest without moving data, resulting in linear $O(n)$ runtime.

How it Works

• 1. Leonardo Numbers: The algorithm partitions the array into chunks of sizes based on Leonardo numbers ($1, 1, 3, 5, 9, 15...$).

• 2. Bitvector Encoding: A bitmask p tracks which Leonardo trees currently exist in the forest. If the last two bits are 11, it means the last two trees have consecutive Leonardo sizes and can potentially be merged.

• 3. Build Forest (Grow): Iterate through the array. For each element, check the bitmask. Either merge the previous two trees into a larger tree (if sizes match Leonardo recurrence) or start a new small tree. This maintains the invariant that tree roots are sorted.

• 4. Trinkle: A unique operation (short for "Tree Sprinkle") that propagates values between the roots of the different trees in the forest. This ensures the global maximum is always at the end of the array.

• 5. Shrink & Sort: Once the array is fully turned into a forest, remove the largest element (at the end). Decompose the root of the largest tree back into its two children, update the bitmask, and re-trinkle to restore order. Repeat until the forest is empty.