Pure implementation of merge-insertion sort algorithm in Python :param collection: some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending Examples: >>> merge_insertion_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5
(collection: list[int])
| 62 | |
| 63 | |
| 64 | def merge_insertion_sort(collection: list[int]) -> list[int]: |
| 65 | """Pure implementation of merge-insertion sort algorithm in Python |
| 66 | |
| 67 | :param collection: some mutable ordered collection with heterogeneous |
| 68 | comparable items inside |
| 69 | :return: the same collection ordered by ascending |
| 70 | |
| 71 | Examples: |
| 72 | >>> merge_insertion_sort([0, 5, 3, 2, 2]) |
| 73 | [0, 2, 2, 3, 5] |
| 74 | |
| 75 | >>> merge_insertion_sort([99]) |
| 76 | [99] |
| 77 | |
| 78 | >>> merge_insertion_sort([-2, -5, -45]) |
| 79 | [-45, -5, -2] |
| 80 | |
| 81 | Testing with all permutations on range(0,5): |
| 82 | >>> import itertools |
| 83 | >>> permutations = list(itertools.permutations([0, 1, 2, 3, 4])) |
| 84 | >>> all(merge_insertion_sort(p) == [0, 1, 2, 3, 4] for p in permutations) |
| 85 | True |
| 86 | """ |
| 87 | |
| 88 | if len(collection) <= 1: |
| 89 | return collection |
| 90 | |
| 91 | """ |
| 92 | Group the items into two pairs, and leave one element if there is a last odd item. |
| 93 | |
| 94 | Example: [999, 100, 75, 40, 10000] |
| 95 | -> [999, 100], [75, 40]. Leave 10000. |
| 96 | """ |
| 97 | two_paired_list = [] |
| 98 | has_last_odd_item = False |
| 99 | for i in range(0, len(collection), 2): |
| 100 | if i == len(collection) - 1: |
| 101 | has_last_odd_item = True |
| 102 | else: |
| 103 | """ |
| 104 | Sort two-pairs in each groups. |
| 105 | |
| 106 | Example: [999, 100], [75, 40] |
| 107 | -> [100, 999], [40, 75] |
| 108 | """ |
| 109 | if collection[i] < collection[i + 1]: |
| 110 | two_paired_list.append([collection[i], collection[i + 1]]) |
| 111 | else: |
| 112 | two_paired_list.append([collection[i + 1], collection[i]]) |
| 113 | |
| 114 | """ |
| 115 | Sort two_paired_list. |
| 116 | |
| 117 | Example: [100, 999], [40, 75] |
| 118 | -> [40, 75], [100, 999] |
| 119 | """ |
| 120 | sorted_list_2d = sortlist_2d(two_paired_list) |
| 121 |
no test coverage detected