Python/sorts/tim_sort.py

from collections.abc import Sequence
from typing import Any, Protocol


class Comparable(Protocol):
    def __lt__(self, other: Any, /) -> bool: ...


def binary_search[T: Comparable](lst: list[T], item: T, start: int, end: int) -> int:
    """>>> binary_search([1, 3, 5], 4, 0, 2)
    2
    >>> binary_search([1, 3, 5], 0, 0, 2)
    0
    >>> binary_search([1, 3, 5], 6, 0, 2)
    3

    Find the insertion index for ``item`` in a sorted sublist.

    It performs a recursive binary search on ``lst`` between indices
    ``start`` and ``end`` (inclusive) and returns the index showing
    where to insert the item so the list stays sorted.

    Args:
        lst: A list of comparable items.
             The sublist from ``start`` to ``end`` must already be sorted.
        item: The value to locate an insertion index for.
        start: Left-most index of the sorted sublist to search.
        end: Right-most index of the sorted sublist to search.

    Returns:
        The index at which ``item`` should be inserted.

    Complexity:
        Time: ``O(log n)`` for the searched sublist.
        Space: ``O(log n)`` due to recursion depth.
    """
    if start == end:
        return start if item < lst[start] else start + 1
    if start > end:
        return start

    mid = (start + end) // 2
    if lst[mid] < item:
        return binary_search(lst, item, mid + 1, end)
    elif item < lst[mid]:
        return binary_search(lst, item, start, mid - 1)
    else:
        return mid


def insertion_sort[T: Comparable](lst: list[T]) -> list[T]:
    """>>> insertion_sort([3, 2, 1])
    [1, 2, 3]

    Return a sorted copy of ``lst`` using insertion sort.

    Uses ``binary_search`` to find where to insert each item. The
    input list is not modified; a new sorted list is returned.

    Args:
        lst: The list to sort. A new list is returned; the input list is
            not modified in-place.

    Returns:
        A new list containing the elements of ``lst`` in ascending order.

    Complexity:
        Time: ``O(n^2)`` in the worst case because each insertion may
            shift many elements.
        Space: ``O(n)`` for the reconstructed list copies.
    """
    length = len(lst)

    for index in range(1, length):
        value = lst[index]
        pos = binary_search(lst, value, 0, index - 1)
        lst = [*lst[:pos], value, *lst[pos:index], *lst[index + 1 :]]

    return lst


def merge[T: Comparable](left: list[T], right: list[T]) -> list[T]:
    """>>> merge([1, 4], [2, 3])
    [1, 2, 3, 4]

    Merge two sorted lists and return a new sorted list.

    Args:
        left: A list sorted in ascending order.
        right: A list sorted in ascending order.

    Returns:
        A new list containing all elements from ``left`` and ``right`` in
        ascending order.

    Complexity:
        Time: ``O(n + m)`` where ``n`` and ``m`` are the input lengths.
        Space: ``O(n + m)`` because recursive slicing creates new lists.
    """
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0], *merge(left[1:], right)]

    return [right[0], *merge(left, right[1:])]


def tim_sort[T: Comparable](lst: Sequence[T]) -> list[T]:
    """
    Sort and return the input using a TimSort-like approach: detect
    runs, sort each run with insertion sort, then merge the runs.

    Complexity:
        Time: ``O(n log n)`` in the common case.
        Space: ``O(n)`` for the extra lists used during sorting.

    >>> tim_sort([])
    []
    >>> tim_sort("Python")
    ['P', 'h', 'n', 'o', 't', 'y']
    >>> tim_sort((1.1, 1, 0, -1, -1.1))
    [-1.1, -1, 0, 1, 1.1]
    >>> tim_sort(list(reversed(list(range(7)))))
    [0, 1, 2, 3, 4, 5, 6]
    >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1])
    True
    >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1])
    True
    >>> tim_sort([1, "a"])
    Traceback (most recent call last):
    ...
    TypeError: '<' not supported between instances of 'str' and 'int'

    """
    if not lst:
        return []
    length = len(lst)
    runs, sorted_runs = [], []
    new_run = [lst[0]]
    sorted_array: list[T] = []
    i = 1
    while i < length:
        if lst[i] < lst[i - 1]:
            runs.append(new_run)
            new_run = [lst[i]]
        else:
            new_run.append(lst[i])
        i += 1
    runs.append(new_run)

    for run in runs:
        sorted_runs.append(insertion_sort(run))
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    return sorted_array


def main() -> None:
    lst = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
    sorted_lst = tim_sort(lst)
    print(sorted_lst)


if __name__ == "__main__":
    main()