Smoothsort Adaptive Heap Sort

Smoothsort is an adaptive heap-based sorting algorithm. It preserves the in-place and worst-case guarantees of heapsort, but it performs much less work when the input is already close to sorted.

You use it when constant extra space matters and the input may contain existing order.

Problem

Given an array ( A ) of length ( n ), sort it in place while taking advantage of nearly sorted input.

The goal is to achieve:

• worst-case ( O(n \log n) ) time
• near-linear behavior on nearly sorted data
• ( O(1) ) extra space

Idea

Smoothsort uses a forest of Leonardo heaps instead of one binary heap. Leonardo heaps have sizes based on Leonardo numbers:

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

These heap sizes allow the algorithm to represent prefixes compactly and merge or split heap structures efficiently.

Algorithm

At a high level:

1. Build a forest of Leonardo heaps over the array
2. Maintain heap order inside each heap
3. Repeatedly remove the maximum element from the forest
4. Split Leonardo heaps as needed during extraction

smoothsort(A):
    forest = empty_leonardo_forest()

    for i in 0..length(A)-1:
        add A[i] to forest
        restore_heap_order(forest)

    for end in length(A)-1 down to 1:
        move_max_to_position(A, forest, end)
        split_or_shrink_forest(forest)
        restore_heap_order(forest)

    return A

Example

Input:

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

The array is almost sorted. Smoothsort can preserve much of the existing order while performing fewer repairs than ordinary heapsort.

Output:

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

Correctness

Smoothsort maintains a forest of heap-ordered Leonardo trees. The maximum element among the active prefix can be identified from the roots. Moving that maximum to the end places it in its final sorted position.

After each extraction, the remaining prefix is restored into valid heap-ordered Leonardo trees. Repeating this process sorts the whole array.

Complexity

Space:

[ O(1) ]

Comparison with Heapsort

When to Use

Use smoothsort when:

• worst-case ( O(n \log n) ) time is required
• extra memory must remain constant
• input is often nearly sorted
• implementation complexity is acceptable

It is mainly useful as a theoretical and systems-level adaptive in-place sort.