Heaps & gaps · Advanced
Smoothsort
Maintain a forest of Leonardo heaps that adapts to existing order, then extract maxima.
- Best
- O(n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(1)
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Grow a forest of Leonardo heaps.
- Sift inside a tree to restore heap order.
- Trinkle across earlier tree roots when necessary.
- Split trees while extracting the maximum suffix.
Why it works
Leonardo-heap roots expose large values while the forest shape can be updated with constant auxiliary state.
Watch for: The forest shape is encoded compactly; roots are repaired with sift and trinkle operations.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.