Smoothsort

Smoothsort is an adaptive comparison-based sorting algorithm designed by Edsger Dijkstra. It is related to heapsort, but it uses a forest of Leonardo heaps instead of one binary heap.

The main advantage is adaptivity. Smoothsort runs in linear time on already sorted or nearly sorted data, while preserving the same worst-case bound as heapsort.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Leonardo Numbers

Smoothsort uses Leonardo numbers as heap sizes.

L(0) = 1,\quad L(1) = 1,\quad L(k) = L(k-1) + L(k-2) + 1

The first values are:

1, 1, 3, 5, 9, 15, 25, 41, \dots

A Leonardo heap of order $k$ has size $L(k)$ .

Key Idea

Smoothsort represents the processed prefix as a forest of Leonardo heaps. These heaps satisfy heap order: each root is at least as large as the values inside that heap.

When the input is close to sorted, the heap construction phase needs little repair. When the input is arbitrary, smoothsort behaves like a heap-based sorting algorithm and keeps the worst-case bound.

Algorithm

smoothsort(A):
    build a forest of Leonardo heaps over A

    while forest is not empty:
        move the maximum root to the end
        remove that root heap from the forest
        if the removed heap has children:
            split it into two Leonardo heaps
            restore heap order among roots

A full implementation is more intricate than binary heapsort because it must encode the current Leonardo heap forest and maintain ordering among heap roots.

Example

Let

A = [5, 1, 4, 2, 3]

Smoothsort builds Leonardo heaps over the prefix. The maximum element becomes available among heap roots. It repeatedly removes the maximum root and repairs the remaining forest.

Final result:

[1,2,3,4,5]

Correctness

Each Leonardo heap maintains heap order, so the maximum element of each heap is stored at its root. The forest root order ensures that the maximum among all remaining elements can be selected and moved to the end. Removing the maximum either deletes a singleton heap or splits a Leonardo heap into its two child heaps. Restoring the invariants after each removal preserves the ability to select the next maximum. Repeating this process outputs elements in decreasing order into the suffix, so the final array is sorted in ascending order.

Complexity

case	time
best, nearly sorted	$O(n)$
worst	$O(n \log n)$
average	$O(n \log n)$

Space complexity:

O(1)

Properties

in-place
not stable
adaptive
comparison-based
same worst-case time as heapsort
faster than heapsort on nearly sorted data

When to Use

Smoothsort is useful when you need an in-place sort with good worst-case behavior and the input may already be close to sorted. It is less common than introsort or timsort because its implementation is complex and difficult to maintain.

Implementation

A production smoothsort implementation is long because it must maintain a compact Leonardo heap forest. The following compact implementation keeps the public interface clear and uses Python’s built-in sorting only as a placeholder for the omitted heap machinery.

def smoothsort(a):
    # Placeholder interface.
    # A full smoothsort implementation maintains Leonardo heaps.
    a.sort()
    return a

For practical code, prefer a tested library implementation. Smoothsort is valuable to study, but hand-written implementations are easy to get wrong.