TheAlgorithms-Python

1
"""
2
This is a pure Python implementation of the merge-insertion sort algorithm
3
Source: https://en.wikipedia.org/wiki/Merge-insertion_sort
4

5
For doctests run following command:
6
python3 -m doctest -v merge_insertion_sort.py
7
or
8
python -m doctest -v merge_insertion_sort.py
9

10
For manual testing run:
11
python3 merge_insertion_sort.py
12
"""
13

14
from __future__ import annotations
15

16

17
def binary_search_insertion(sorted_list, item):
18
    """
19
    >>> binary_search_insertion([1, 2, 7, 9, 10], 4)
20
    [1, 2, 4, 7, 9, 10]
21
    """
22
    left = 0
23
    right = len(sorted_list) - 1
24
    while left <= right:
25
        middle = (left + right) // 2
26
        if left == right:
27
            if sorted_list[middle] < item:
28
                left = middle + 1
29
            break
30
        elif sorted_list[middle] < item:
31
            left = middle + 1
32
        else:
33
            right = middle - 1
34
    sorted_list.insert(left, item)
35
    return sorted_list
36

37

38
def merge(left, right):
39
    """
40
    >>> merge([[1, 6], [9, 10]], [[2, 3], [4, 5], [7, 8]])
41
    [[1, 6], [2, 3], [4, 5], [7, 8], [9, 10]]
42
    """
43
    result = []
44
    while left and right:
45
        if left[0][0] < right[0][0]:
46
            result.append(left.pop(0))
47
        else:
48
            result.append(right.pop(0))
49
    return result + left + right
50

51

52
def sortlist_2d(list_2d):
53
    """
54
    >>> sortlist_2d([[9, 10], [1, 6], [7, 8], [2, 3], [4, 5]])
55
    [[1, 6], [2, 3], [4, 5], [7, 8], [9, 10]]
56
    """
57
    length = len(list_2d)
58
    if length <= 1:
59
        return list_2d
60
    middle = length // 2
61
    return merge(sortlist_2d(list_2d[:middle]), sortlist_2d(list_2d[middle:]))
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

122
    """
123
    40 < 100 is sure because it has already been sorted.
124
    Generate the sorted_list of them so that you can avoid unnecessary comparison.
125

126
    Example:
127
           group0 group1
128
           40     100
129
           75     999
130
        ->
131
           group0 group1
132
           [40,   100]
133
           75     999
134
    """
135
    result = [i[0] for i in sorted_list_2d]
136

137
    """
138
    100 < 999 is sure because it has already been sorted.
139
    Put 999 in last of the sorted_list so that you can avoid unnecessary comparison.
140

141
    Example:
142
           group0 group1
143
           [40,   100]
144
           75     999
145
        ->
146
           group0 group1
147
           [40,   100,   999]
148
           75
149
    """
150
    result.append(sorted_list_2d[-1][1])
151

152
    """
153
    Insert the last odd item left if there is.
154

155
    Example:
156
           group0 group1
157
           [40,   100,   999]
158
           75
159
        ->
160
           group0 group1
161
           [40,   100,   999,   10000]
162
           75
163
    """
164
    if has_last_odd_item:
165
        pivot = collection[-1]
166
        result = binary_search_insertion(result, pivot)
167

168
    """
169
    Insert the remaining items.
170
    In this case, 40 < 75 is sure because it has already been sorted.
171
    Therefore, you only need to insert 75 into [100, 999, 10000],
172
    so that you can avoid unnecessary comparison.
173

174
    Example:
175
           group0 group1
176
           [40,   100,   999,   10000]
177
            ^ You don't need to compare with this as 40 < 75 is already sure.
178
           75
179
        ->
180
           [40,   75,    100,   999,   10000]
181
    """
182
    is_last_odd_item_inserted_before_this_index = False
183
    for i in range(len(sorted_list_2d) - 1):
184
        if result[i] == collection[-1] and has_last_odd_item:
185
            is_last_odd_item_inserted_before_this_index = True
186
        pivot = sorted_list_2d[i][1]
187
        # If last_odd_item is inserted before the item's index,
188
        # you should forward index one more.
189
        if is_last_odd_item_inserted_before_this_index:
190
            result = result[: i + 2] + binary_search_insertion(result[i + 2 :], pivot)
191
        else:
192
            result = result[: i + 1] + binary_search_insertion(result[i + 1 :], pivot)
193

194
    return result
195

196

197
if __name__ == "__main__":
198
    user_input = input("Enter numbers separated by a comma:\n").strip()
199
    unsorted = [int(item) for item in user_input.split(",")]
200
    print(merge_insertion_sort(unsorted))
201