TheAlgorithms-Python

1
"""
2
Implementation of iterative merge sort in Python
3
Author: Aman Gupta
4

5
For doctests run following command:
6
python3 -m doctest -v iterative_merge_sort.py
7

8
For manual testing run:
9
python3 iterative_merge_sort.py
10
"""
11

12
from __future__ import annotations
13

14

15
def merge(input_list: list, low: int, mid: int, high: int) -> list:
16
    """
17
    sorting left-half and right-half individually
18
    then merging them into result
19
    """
20
    result = []
21
    left, right = input_list[low:mid], input_list[mid : high + 1]
22
    while left and right:
23
        result.append((left if left[0] <= right[0] else right).pop(0))
24
    input_list[low : high + 1] = result + left + right
25
    return input_list
26

27

28
# iteration over the unsorted list
29
def iter_merge_sort(input_list: list) -> list:
30
    """
31
    Return a sorted copy of the input list
32

33
    >>> iter_merge_sort([5, 9, 8, 7, 1, 2, 7])
34
    [1, 2, 5, 7, 7, 8, 9]
35
    >>> iter_merge_sort([1])
36
    [1]
37
    >>> iter_merge_sort([2, 1])
38
    [1, 2]
39
    >>> iter_merge_sort([2, 1, 3])
40
    [1, 2, 3]
41
    >>> iter_merge_sort([4, 3, 2, 1])
42
    [1, 2, 3, 4]
43
    >>> iter_merge_sort([5, 4, 3, 2, 1])
44
    [1, 2, 3, 4, 5]
45
    >>> iter_merge_sort(['c', 'b', 'a'])
46
    ['a', 'b', 'c']
47
    >>> iter_merge_sort([0.3, 0.2, 0.1])
48
    [0.1, 0.2, 0.3]
49
    >>> iter_merge_sort(['dep', 'dang', 'trai'])
50
    ['dang', 'dep', 'trai']
51
    >>> iter_merge_sort([6])
52
    [6]
53
    >>> iter_merge_sort([])
54
    []
55
    >>> iter_merge_sort([-2, -9, -1, -4])
56
    [-9, -4, -2, -1]
57
    >>> iter_merge_sort([1.1, 1, 0.0, -1, -1.1])
58
    [-1.1, -1, 0.0, 1, 1.1]
59
    >>> iter_merge_sort(['c', 'b', 'a'])
60
    ['a', 'b', 'c']
61
    >>> iter_merge_sort('cba')
62
    ['a', 'b', 'c']
63
    """
64
    if len(input_list) <= 1:
65
        return input_list
66
    input_list = list(input_list)
67

68
    # iteration for two-way merging
69
    p = 2
70
    while p <= len(input_list):
71
        # getting low, high and middle value for merge-sort of single list
72
        for i in range(0, len(input_list), p):
73
            low = i
74
            high = i + p - 1
75
            mid = (low + high + 1) // 2
76
            input_list = merge(input_list, low, mid, high)
77
        # final merge of last two parts
78
        if p * 2 >= len(input_list):
79
            mid = i
80
            input_list = merge(input_list, 0, mid, len(input_list) - 1)
81
            break
82
        p *= 2
83

84
    return input_list
85

86

87
if __name__ == "__main__":
88
    user_input = input("Enter numbers separated by a comma:\n").strip()
89
    if user_input == "":
90
        unsorted = []
91
    else:
92
        unsorted = [int(item.strip()) for item in user_input.split(",")]
93
    print(iter_merge_sort(unsorted))
94