(lst)
| 42 | |
| 43 | |
| 44 | def timsort(lst): |
| 45 | runs, sorted_runs = [], [] |
| 46 | length = len(lst) |
| 47 | new_run = [lst[0]] |
| 48 | sorted_array = [] |
| 49 | |
| 50 | for i in range(1, length): |
| 51 | if i == length - 1: |
| 52 | new_run.append(lst[i]) |
| 53 | runs.append(new_run) |
| 54 | break |
| 55 | |
| 56 | if lst[i] < lst[i - 1]: |
| 57 | if not new_run: |
| 58 | runs.append([lst[i - 1]]) |
| 59 | new_run.append(lst[i]) |
| 60 | else: |
| 61 | runs.append(new_run) |
| 62 | new_run = [] |
| 63 | else: |
| 64 | new_run.append(lst[i]) |
| 65 | |
| 66 | for run in runs: |
| 67 | sorted_runs.append(insertion_sort(run)) |
| 68 | |
| 69 | for run in sorted_runs: |
| 70 | sorted_array = merge(sorted_array, run) |
| 71 | |
| 72 | return sorted_array |
| 73 | |
| 74 | |
| 75 | def main(): |
no test coverage detected