>>> 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]) ==
(lst: list[Any] | tuple[Any, ...] | str)
| 41 | |
| 42 | |
| 43 | def tim_sort(lst: list[Any] | tuple[Any, ...] | str) -> list[Any]: |
| 44 | """ |
| 45 | >>> tim_sort("Python") |
| 46 | ['P', 'h', 'n', 'o', 't', 'y'] |
| 47 | >>> tim_sort((1.1, 1, 0, -1, -1.1)) |
| 48 | [-1.1, -1, 0, 1, 1.1] |
| 49 | >>> tim_sort(list(reversed(list(range(7))))) |
| 50 | [0, 1, 2, 3, 4, 5, 6] |
| 51 | >>> tim_sort([3, 2, 1]) == insertion_sort([3, 2, 1]) |
| 52 | True |
| 53 | >>> tim_sort([3, 2, 1]) == sorted([3, 2, 1]) |
| 54 | True |
| 55 | """ |
| 56 | length = len(lst) |
| 57 | runs, sorted_runs = [], [] |
| 58 | new_run = [lst[0]] |
| 59 | sorted_array: list[Any] = [] |
| 60 | i = 1 |
| 61 | while i < length: |
| 62 | if lst[i] < lst[i - 1]: |
| 63 | runs.append(new_run) |
| 64 | new_run = [lst[i]] |
| 65 | else: |
| 66 | new_run.append(lst[i]) |
| 67 | i += 1 |
| 68 | runs.append(new_run) |
| 69 | |
| 70 | for run in runs: |
| 71 | sorted_runs.append(insertion_sort(run)) |
| 72 | for run in sorted_runs: |
| 73 | sorted_array = merge(sorted_array, run) |
| 74 | |
| 75 | return sorted_array |
| 76 | |
| 77 | |
| 78 | def main(): |
no test coverage detected