Interactive demo
Smoothsort Visualization
Smoothsort, invented by Edsger W. Dijkstra in 1981, is a heapsort that adapts to presorted data. Instead of one heap it keeps a forest of heaps whose sizes are Leonardo numbers, and on sorted input it barely has to move anything.
Choose “Sorted” as the starting order: hardly anything moves. The trees above the array show the heaps; their roots ascend from left to right.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element in the heap forest
- Element moving down
- Compared child
- Larger element
- Final position
Runtime and properties
Best case
O(n)
On sorted input nothing has to move: each element only costs a few comparisons.
Average case
O(n log n)
Like heapsort, every element sinks through about log n levels.
Worst case
O(n log n)
The heaps never get deeper than about log n levels.
Extra memory
O(1)
The heaps live in the array; the forest's shape fits in a few variables.
Stable
No
Swaps between roots and children jump over equal elements.
In-place
Yes
The heaps are built and taken apart within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort this page | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Leonardo heaps
The heaps have 1, 1, 3, 5, 9, 15 … elements: the Leonardo numbers, where each one is the sum of the two before plus 1. A heap of order k consists of a root with heaps of order k − 1 and k − 2 below it.
2. Building the forest
Every new element either joins the two rightmost heaps as their new root or starts a heap of its own. Then it moves left along the roots and down into its heap until the roots ascend and every root is the largest of its heap.
3. Taking it apart
The rightmost root is always the largest element, so it is already at its final position. Removing it leaves its two subtrees as heaps of their own, which only have to be fitted into the row of roots.
Credits
- Smoothsort was introduced by Edsger W. Dijkstra in his note EWD796a, “Smoothsort, an alternative for sorting in situ”. This visualization follows its idea with a plain list of the heaps instead of Dijkstra's compact bookkeeping.