fix(sorts): make smoothsort generic over Comparable items

@@ -10,14 +10,21 @@     https://www.cs.utexas.edu/~EWD/ewd07xx/EWD796a.PDF """ +from typing import Any, Protocol+++class Comparable(Protocol):+    def __lt__(self, other: Any, /) -> bool: ...++ # Precomputed Leonardo numbers: L(0)=1, L(1)=1, L(k)=L(k-1)+L(k-2)+1. # 46 values comfortably cover all practical list sizes. _LEONARDO: list[int] = [1, 1] while _LEONARDO[-1] < 2**31:     _LEONARDO.append(_LEONARDO[-1] + _LEONARDO[-2] + 1)  -def _sift(seq: list[int], root: int, order: int) -> None:+def _sift[T: Comparable](seq: list[T], root: int, order: int) -> None:     """     Restore the max-heap property within a Leonardo tree of the given ``order``. @@ -59,20 +66,20 @@ def _sift(seq: list[int], root: int, order: int) -> None:         right = root - 1  # right child root         left = root - 1 - _LEONARDO[order - 2]  # left child root -        if seq[left] >= seq[right] and seq[left] > seq[root]:+        if not (seq[left] < seq[right]) and seq[root] < seq[left]:             seq[root], seq[left] = seq[left], seq[root]             root = left             order -= 1-        elif seq[right] > seq[left] and seq[right] > seq[root]:+        elif seq[left] < seq[right] and seq[root] < seq[right]:             seq[root], seq[right] = seq[right], seq[root]             root = right             order -= 2         else:             break  -def _trinkle(-    seq: list[int],+def _trinkle[T: Comparable](+    seq: list[T],     pos: int,     heap_sizes: list[int],     idx: int,@@ -105,14 +112,14 @@ def _trinkle(     """     while idx > 0:         prev_root = pos - _LEONARDO[heap_sizes[idx]]-        if seq[pos] >= seq[prev_root]:+        if not (seq[pos] < seq[prev_root]):             break-        # Only swap if prev_root is also >= its own children; otherwise+        # Only swap if prev_root is also > its own children; otherwise         # moving it would break the heap on the left side.         if heap_sizes[idx] > 1:             right = pos - 1             left = pos - 1 - _LEONARDO[heap_sizes[idx] - 2]-            if seq[prev_root] <= seq[right] or seq[prev_root] <= seq[left]:+            if not (seq[right] < seq[prev_root]) or not (seq[left] < seq[prev_root]):                 break         seq[pos], seq[prev_root] = seq[prev_root], seq[pos]         pos = prev_root@@ -121,7 +128,7 @@ def _trinkle(     _sift(seq, pos, heap_sizes[idx])  -def smoothsort(seq: list[int]) -> list[int]:+def smoothsort[T: Comparable](seq: list[T]) -> list[T]:     """     Sort a list in-place using the Smoothsort algorithm and return it. @@ -131,7 +138,7 @@ def smoothsort(seq: list[int]) -> list[int]:     whose structure mirrors the sorted prefix of the sequence.      Args:-        seq: A list of integers to sort.+        seq: A list of mutually comparable items to sort.      Returns:         The same list object, sorted in ascending order.@@ -147,10 +154,18 @@ def smoothsort(seq: list[int]) -> list[int]:         [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'     """     n = len(seq)     if n < 2:

@@ -51,6 +51,7 @@ from sorts.selection_sort import selection_sort from sorts.shell_sort import shell_sort from sorts.shrink_shell_sort import shell_sort as shrink_shell_sort+from sorts.smoothsort import smoothsort from sorts.stooge_sort import stooge_sort from sorts.strand_sort import strand_sort from sorts.tim_sort import tim_sort@@ -92,6 +93,7 @@ def test_heap_sort() -> None:     selection_sort,     shell_sort,     shrink_shell_sort,+    smoothsort,     stooge_sort,     strand_sort,     three_way_radix_quicksort,