>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] >>> max_depth = 2 * math.ceil(math.log2(len(array))) >>> intro_sort(array, 0, len(array), 16, max_depth) [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79]
(
array: list, start: int, end: int, size_threshold: int, max_depth: int
)
| 164 | |
| 165 | |
| 166 | def intro_sort( |
| 167 | array: list, start: int, end: int, size_threshold: int, max_depth: int |
| 168 | ) -> list: |
| 169 | """ |
| 170 | >>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] |
| 171 | >>> max_depth = 2 * math.ceil(math.log2(len(array))) |
| 172 | >>> intro_sort(array, 0, len(array), 16, max_depth) |
| 173 | [1, 2, 4, 6, 7, 8, 8, 12, 14, 14, 22, 23, 27, 45, 56, 79] |
| 174 | """ |
| 175 | while end - start > size_threshold: |
| 176 | if max_depth == 0: |
| 177 | return heap_sort(array) |
| 178 | max_depth -= 1 |
| 179 | pivot = median_of_3(array, start, start + ((end - start) // 2) + 1, end - 1) |
| 180 | p = partition(array, start, end, pivot) |
| 181 | intro_sort(array, p, end, size_threshold, max_depth) |
| 182 | end = p |
| 183 | return insertion_sort(array, start, end) |
| 184 | |
| 185 | |
| 186 | if __name__ == "__main__": |
no test coverage detected