Smoothsort in Python
In-place heap-based sort using Leonardo heaps; O(n) on sorted input and O(n log n) worst case.
- File
smoothsort.py, 81 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/smoothsort/. The authors are listed in prov/WX5SGY.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def leonardo(limit: int) -> list[int]:
"""Return the Leonardo numbers 1, 1, 3, 5, 9, 15, ... up to the first one above limit."""
nums = [1, 1]
while nums[-1] <= limit:
nums.append(nums[-1] + nums[-2] + 1)
return nums
def sift_down(a: list[T], root: int, order: int, lp: list[int]) -> None:
"""Restore the max-heap order of the Leonardo tree of the given order whose root is at index root."""
while order >= 2:
right = root - 1 # the root of the subtree of order - 2
left = right - lp[order - 2] # the root of the subtree of order - 1
if a[left] < a[right]:
child, child_order = right, order - 2
else:
child, child_order = left, order - 1
if not a[root] < a[child]:
return
a[root], a[child] = a[child], a[root]
root, order = child, child_order
def rectify(a: list[T], trees: list[tuple[int, int]], j: int, lp: list[int]) -> None:
"""Make the roots of trees[0..j] ascending and tree j a max-heap, assuming the others are."""
root, order = trees[j]
while j > 0:
prev = trees[j - 1][0]
big = root
if order >= 2:
right = root - 1
left = right - lp[order - 2]
if a[big] < a[left]:
big = left
if a[big] < a[right]:
big = right
if not a[big] < a[prev]:
break
a[root], a[prev] = a[prev], a[root]
j -= 1
root, order = trees[j]
sift_down(a, root, order, lp)
def smoothsort(a: list[T]) -> None:
"""Sort the list a in place, in non-decreasing order."""
n = len(a)
lp = leonardo(n)
trees: list[tuple[int, int]] = [] # @line L1: (root index, order), from left to right
for i in range(n): # @line L2
if len(trees) >= 2 and trees[-2][1] == trees[-1][1] + 1: # @line L3
order = trees[-2][1] + 1
del trees[-2:]
trees.append((i, order))
elif trees and trees[-1][1] == 1: # @line L4
trees.append((i, 0))
else:
trees.append((i, 1))
rectify(a, trees, len(trees) - 1, lp) # @line L5
for i in range(n - 1, 0, -1): # @line L6
root, order = trees.pop() # @line L7: a[i] is the largest item left
if order >= 2: # @line L8
right = root - 1
left = right - lp[order - 2]
trees.append((left, order - 1))
rectify(a, trees, len(trees) - 1, lp) # @line L9
trees.append((right, order - 2))
rectify(a, trees, len(trees) - 1, lp)
test_smoothsort.py 58 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/smoothsort/. The authors are listed in prov/WX5SGY.jsonl.
import itertools
import random
from smoothsort import leonardo, smoothsort
count = [0]
class Counted:
__slots__ = ("k",)
def __init__(self, k: int) -> None:
self.k = k
def __lt__(self, other: "Counted") -> bool:
count[0] += 1
return self.k < other.k
def comparisons(keys: list[int]) -> int:
count[0] = 0
b = [Counted(k) for k in keys]
smoothsort(b)
assert [x.k for x in b] == sorted(keys)
return count[0]
def test_leonardo() -> None:
assert leonardo(100) == [1, 1, 3, 5, 9, 15, 25, 41, 67, 109]
def test_example() -> None:
assert comparisons([7, 2, 9, 4, 1, 8, 3, 6]) == 33
def test_all_permutations() -> None:
for n in range(8):
for p in itertools.permutations(range(n)):
b = list(p)
smoothsort(b)
assert b == list(range(n))
def test_sorted_input_is_linear() -> None:
for n in (100, 1000, 10000):
assert comparisons(list(range(n))) <= 6 * n
def test_random_against_sorted() -> None:
rng = random.Random(3)
for _ in range(200):
a = [rng.randint(-20, 20) for _ in range(rng.randint(0, 300))]
b = list(a)
smoothsort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build