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

Classes

Comparable

Base class for protocol classes.

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[T])	Sort a list in-place using the Smoothsort algorithm and return it.

Module Contents

class sorts.smoothsort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: Any, /) → bool

sorts.smoothsort._sift[T: Comparable](seq: list[T], 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[T: Comparable](seq: list[T], 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[T: Comparable](seq: list[T]) → list[T]

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 mutually comparable items 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(["d", "a", "c", "b"])
['a', 'b', 'c', 'd']
>>> smoothsort([2.5, -1, 0.0])
[-1, 0.0, 2.5]
>>> smoothsort([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
>>> smoothsort([-3, 0, -1, 5, 2])
[-3, -1, 0, 2, 5]
>>> smoothsort([1, "a"])
Traceback (most recent call last):
    ...
TypeError: '<' not supported between instances of 'str' and 'int'

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

sorts.smoothsort.results