sorts.smoothsort

Smoothsort algorithm implementation.

Smoothsort is an adaptive, in-place comparison sort invented by Edsger W. Dijkstra. It runs in O(n log n) worst-case and degrades gracefully to O(n) for nearly sorted data. It uses a forest of Leonardo heaps to achieve this adaptive behaviour.

Reference:

https://en.wikipedia.org/wiki/Smoothsort https://www.cs.utexas.edu/~EWD/ewd07xx/EWD796a.PDF

Attributes

_LEONARDO
results

Functions

_sift(→ None)	Restore the max-heap property within a Leonardo tree of the given order.
_trinkle(→ None)	Restore both the inter-heap root ordering and the intra-heap ordering.
smoothsort(→ list[int])	Sort a list in-place using the Smoothsort algorithm and return it.

Module Contents

sorts.smoothsort._sift(seq: list[int], root: int, order: int) → None

Restore the max-heap property within a Leonardo tree of the given order.

Sifts seq[root] downward until the subtree satisfies the Leonardo max-heap invariant: every node is >= both of its children. Trees of order 0 or 1 are single nodes and already satisfy the invariant.

In a Leonardo tree of order k rooted at index root:

• the right child root is at root - 1

• the left child root is at root - 1 - L(k-2)

Args:

seq: The list being sorted (mutated in-place). root: Index of the root of the Leonardo tree to fix. order: Leonardo order of the tree rooted at root.

Examples:

>>> data = [3, 5, 4]
>>> _sift(data, 2, 2)
>>> data
[3, 4, 5]

>>> data = [1, 2, 3]
>>> _sift(data, 2, 2)
>>> data
[1, 2, 3]

>>> data = [7]
>>> _sift(data, 0, 1)
>>> data
[7]

>>> data = [9, 1, 8, 5, 3]
>>> _sift(data, 4, 3)
>>> data
[3, 1, 9, 5, 8]

sorts.smoothsort._trinkle(seq: list[int], pos: int, heap_sizes: list[int], idx: int) → None

Restore both the inter-heap root ordering and the intra-heap ordering.

Walks the value at pos leftwards through the forest-root chain as long as the left-neighbour root is larger, then calls _sift to fix the heap at the final resting position.

Args:

seq: The list being sorted (mutated in-place). pos: Index of the root being inserted or newly exposed. heap_sizes: List of Leonardo orders for the current forest (left to

right); heap_sizes[idx] is the order of the tree whose root is at pos.

idx: Position in heap_sizes for the tree rooted at pos.

Examples:

>>> data = [1, 5, 3]
>>> _trinkle(data, 2, [1, 1], 1)
>>> data
[1, 3, 5]

>>> data = [3, 5, 4]
>>> _trinkle(data, 2, [2], 0)
>>> data
[3, 4, 5]

sorts.smoothsort.smoothsort(seq: list[int]) → list[int]

Sort a list in-place using the Smoothsort algorithm and return it.

Smoothsort (Edsger W. Dijkstra, 1981) is an adaptive, in-place sort with O(n log n) worst-case time and O(n) best-case time on already-sorted input. It improves on Heapsort by maintaining a forest of Leonardo heaps whose structure mirrors the sorted prefix of the sequence.

Args:

seq: A list of integers to sort.

Returns:

The same list object, sorted in ascending order.

Examples:

>>> smoothsort([4, 1, 3, 9, 7])
[1, 3, 4, 7, 9]
>>> smoothsort([])
[]
>>> smoothsort([1])
[1]
>>> smoothsort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]
>>> smoothsort([3, 3, 2, 1, 2])
[1, 2, 2, 3, 3]
>>> smoothsort([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
>>> smoothsort([-3, 0, -1, 5, 2])
[-3, -1, 0, 2, 5]

sorts.smoothsort._LEONARDO: list[int] = [1, 1]

sorts.smoothsort.results