sorts.tim_sort

Functions

binary_search(→ int)

insertion_sort(→ list[Any])

main(→ None)

merge(→ list[Any])

tim_sort(→ list[Any])

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

Module Contents

>>> 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(lst: list[Any]) → list[Any]
>>> 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(left: list[Any], right: list[Any]) → list[Any]
>>> 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(lst: list[Any] | tuple[Any, ...] | str) → list[Any]

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