How to Learn Smoothsort: Leonardo Heaps, Adaptive In-Place Sorting, Heap Forests and Nearly Sorted Data

Wait, What?

A heapsort relative can notice that the data is already almost sorted—and avoid doing the full amount of work.

Classic heapsort gives dependable O(n log n) worst-case performance and uses little extra storage, but it does not naturally become linear just because the input is already ordered. Edsger W. Dijkstra designed smoothsort to keep the in-place and worst-case strengths of heap-based sorting while adapting to existing order.

Smoothsort is famous partly because it is clever and partly because it is difficult to implement correctly. That makes it an excellent Learning Hall algorithm: the goal is not merely to memorise code, but to learn why Leonardo numbers describe a heap forest, how invariants carry the algorithm, how adaptivity differs from average-case speed, and when a sophisticated algorithm is worth—or not worth—its engineering cost.

Quick Answer

Learn smoothsort in this order: heapsort idea → adaptivity → Leonardo numbers → forest of Leonardo heaps → heap roots → build phase → sift and trinkle ideas → root ordering → extraction phase → O(n log n) worst case → O(n) on already sorted input → implementation complexity → compare with modern adaptive mergesorts.

1. Begin With the Problem Smoothsort Tries to Fix

Suppose an array is already sorted. A conventional comparison sort may still perform substantial work because it does not use that fact. An adaptive sorting algorithm changes its work according to some measure of presortedness.

Smoothsort’s striking promise is:

worst case: O(n log n);
already sorted input: O(n);
in-place operation: O(1) auxiliary storage in the algorithmic sense.

The word “smooth” points to the transition between ordered and disordered cases.

2. Review Heapsort First

Heapsort normally builds one binary heap. The maximum element sits at the root, then the algorithm repeatedly moves that maximum to the end and restores the heap property.

Smoothsort uses the same broad pattern—organise, expose an extreme, extract—but it does not represent the prefix as one ordinary binary heap. It represents the prefix as a forest of specially sized heaps.

3. Meet the Leonardo Numbers

Smoothsort uses the Leonardo sequence:

L(0) = 1
L(1) = 1
L(k) = L(k-1) + L(k-2) + 1

The first values are:

1, 1, 3, 5, 9, 15, 25, 41, ...

The recurrence is not decorative. A Leonardo heap of order k can be formed from a heap of order k−1, a heap of order k−2, and one new root. The sizes therefore fit contiguous array segments without explicit pointer-based tree nodes.

4. A Leonardo Heap Is a Shape Constraint Plus a Heap Constraint

Conceptually, a Leonardo heap of order k has:

a root;
a left child heap of order k−1;
a right child heap of order k−2;
a heap-order condition placing the root at least as large as the child roots for a max-oriented sort.

The exact array-index arithmetic is one of the difficult implementation parts, so learners should first understand the recursive shape before studying bit encodings or optimised code.

5. Why a Forest Instead of One Heap?

Not every prefix length is a Leonardo number. Smoothsort therefore decomposes the current prefix into several Leonardo heaps whose sizes sum to the prefix length.

Think of the array prefix as:

[heap][heap][heap]...[heap]

with heap orders tracked compactly. This forest representation lets the algorithm extend the prefix one element at a time while reusing structural work already present in the input.

6. The Build Phase Grows the Forest

As the scan moves from left to right, a new item is incorporated into the heap forest. Depending on the orders of the rightmost heaps, the algorithm either:

merges two appropriately sized neighbouring Leonardo heaps under the new element; or
starts a new small Leonardo heap.

After the structural change, local heap-order restoration is performed only as needed.

7. “Sift” Restores Order Inside One Leonardo Heap

The sift idea is related to binary-heap sifting: compare a root with child roots, move the larger child upward when necessary, and continue down the selected child heap until the heap property is restored.

The geometry differs from a binary heap because the two child heaps have different Leonardo orders, but the invariant is familiar:

root >= both child roots

8. “Trinkle” Handles the Forest-Level Order

Smoothsort also needs to respect relationships between roots of neighbouring heaps in the forest. Dijkstra’s presentation uses operations commonly described as trinkle and related variants to move a value through the chain of heap roots while preserving the internal heap structures.

For a learner, the important distinction is:

sift: repair inside one Leonardo heap;
trinkle: repair with awareness of preceding heap roots in the forest.

Do not start with the compressed production implementation. Start with these two invariants.

9. Why Sorted Input Becomes Cheap

If the array is already increasing, the newly added elements tend already to dominate earlier heap roots. Much of the expensive rearrangement becomes unnecessary. The structure can be recognised and maintained with essentially linear total work.

This is the key adaptive idea: smoothsort does not merely have a lucky constant factor on sorted data; Dijkstra’s design gives linear behaviour for that case.

10. The Extraction Phase Shrinks the Forest

Once the full array has been represented by a valid heap forest, the largest remaining element is placed at the right end. Then the rightmost Leonardo heap is reduced.

If a larger Leonardo heap is split, its two child heaps reappear as separate heaps in the forest. Their roots may need local restoration against the preceding roots. The sorted suffix grows from right to left until nothing remains unsorted.

11. A Conceptual Pseudocode Skeleton

smoothsort(A):
    forest = empty Leonardo-heap description

    for each next position q from left to right:
        extend forest to include A[q]
        if rightmost heap relationships need repair:
            restore heap/forest invariants

    while unsorted prefix is not empty:
        place current maximum at end of prefix
        shrink or split rightmost Leonardo heap
        repair exposed heaps only as needed

This is deliberately not drop-in implementation code. Smoothsort is one of those algorithms where understanding the state representation before coding is more valuable than copying a dense reference routine.

12. The Compact State Is Part of the Difficulty

Efficient implementations encode which Leonardo heap orders are present using a bit pattern plus an order index. That is elegant because the forest shape can be represented with very little extra state.

It is also where many implementation errors begin. A professional implementation must keep several facts synchronised:

which heap orders exist;
where each heap root is in the array;
where its two child roots are;
which roots are trusted to satisfy heap order;
which prefix/suffix boundary is currently active.

13. Complexity: Separate Guarantees From Workload Behaviour

Smoothsort retains O(n log n) worst-case comparison complexity. For an already sorted sequence, it runs in O(n). Nearly sorted data can also benefit, although the exact amount depends on the disorder pattern.

That makes smoothsort a useful example of three different questions:

What is the worst-case asymptotic bound?
What structure in the input can the algorithm exploit?
Does the implementation complexity and machine behaviour make it competitive in the target environment?

14. Smoothsort Is Not Automatically the Best Modern General Sort

A theoretically attractive adaptive property does not automatically make an algorithm the best library default. Modern general-purpose sorting systems care about cache locality, branch prediction, stable ordering, run detection, move cost, vectorisation and implementation maintainability.

That is why adaptive merge-family algorithms such as Timsort/Powersort-style designs are important comparisons. Smoothsort is especially valuable as a study in in-place adaptivity and invariant design, not as a claim that every standard library should replace its current sort.

15. Common Failure States

Trying to code from the Leonardo recurrence without understanding the heap forest.
Confusing the forest-level root order with the internal heap property.
Using Fibonacci numbers instead of Leonardo numbers.
Getting child-root index arithmetic wrong after a split.
Updating the bit-encoded heap description out of sync with the array.
Assuming “adaptive” means O(n) for every vaguely nearly sorted input.
Benchmarking one input distribution and generalising to all workloads.
Choosing smoothsort solely from asymptotic notation without measuring implementation costs.

16. Build Tests Around Structure

Useful tests include:

empty and one-element arrays;
already sorted input;
reverse-sorted input;
all equal values;
small arrays around Leonardo sizes 1, 3, 5, 9, 15 and 25;
lengths just below and just above those boundaries;
random permutations;
arrays with one displaced element;
large duplicate-heavy inputs;
property testing against a trusted reference sort.

For every run, verify sortedness and preservation of the input multiset.

17. Practice Ladder: Beginner to Professional

Beginner: review binary heaps and heapsort with small arrays.
Foundation: generate Leonardo numbers and draw Leonardo heaps of orders 2, 3 and 4.
Intermediate: decompose prefix lengths into a forest and track the rightmost heap orders.
Advanced: trace sift and forest-root restoration separately before combining them.
Professional: implement with assertions around every invariant, differential-test against a trusted sort, benchmark ordered/random/partially ordered inputs, and compare maintainability with modern adaptive sorts.
Transfer: explain the difference between a worst-case guarantee and an algorithm exploiting presortedness.

18. A Better Way to Study Smoothsort

Do not begin by transcribing Dijkstra’s compact notation into code. First build a visible table with columns for array prefix, Leonardo heap orders, heap roots, trusted invariants, next structural operation. Predict the next forest shape, then run a reference trace and compare.

Only after the structural trace becomes easy should you compress the forest description into bits. This follows research-informed programming pedagogy: read and predict before writing, make hidden state visible, reduce cognitive load with worked examples, and fade scaffolding as the learner gains fluency.

Learning Hall Boundary

This article owns smoothsort as an adaptive, in-place comparison sort built from Leonardo heaps and a compact heap forest. It complements existing heaps, sorting and modern Timsort/Powersort material without replacing their canonical jobs. It does not take over MindOS, Bolt or Student/Studying Interface ownership.

Evidence Boundary

The canonical source is Edsger W. Dijkstra’s 1981 manuscript EWD796a, “Smoothsort, an alternative for sorting in situ”. NIST’s Dictionary of Algorithms and Data Structures summarises smoothsort as O(n) for sorted input and O(n log n) in the worst case. For the wider adaptive-sorting comparison, modern research on natural mergesorts shows why presorted runs are also exploited by other algorithm families. The learning progression is informed by CS2023 and the Raspberry Pi Foundation’s research-informed programming pedagogy, including code reading, tracing and PRIMM-style gradual release.

Professional rule: you understand smoothsort when you can explain why Leonardo heaps fit an in-place forest, identify the separate heap and forest invariants, and justify when adaptivity is valuable without pretending that theoretical elegance removes implementation and machine-level trade-offs.

Small Group Tutorials