sorts.tim_sort

Classes

Comparable

Base class for protocol classes.

Functions

binary_search(→ int)

insertion_sort(→ list[T])

main(→ None)

merge(→ list[T])

tim_sort(→ list[T])

Sort and return the input using a TimSort-like approach: detect

Module Contents

class sorts.tim_sort.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
>>> 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.

sorts.tim_sort.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.

sorts.tim_sort.main() → None
sorts.tim_sort.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.

sorts.tim_sort.tim_sort[T: Comparable](lst: collections.abc.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'