TheAlgorithms-Python

1
"""
2
This is a pure Python implementation of the merge sort algorithm.
3

4
For doctests run following command:
5
python -m doctest -v merge_sort.py
6
or
7
python3 -m doctest -v merge_sort.py
8
For manual testing run:
9
python merge_sort.py
10
"""
11

12

13
def merge_sort(collection: list) -> list:
14
    """
15
    Sorts a list using the merge sort algorithm.
16

17
    :param collection: A mutable ordered collection with comparable items.
18
    :return: The same collection ordered in ascending order.
19

20
    Time Complexity: O(n log n)
21

22
    Examples:
23
    >>> merge_sort([0, 5, 3, 2, 2])
24
    [0, 2, 2, 3, 5]
25
    >>> merge_sort([])
26
    []
27
    >>> merge_sort([-2, -5, -45])
28
    [-45, -5, -2]
29
    """
30

31
    def merge(left: list, right: list) -> list:
32
        """
33
        Merge two sorted lists into a single sorted list.
34

35
        :param left: Left collection
36
        :param right: Right collection
37
        :return: Merged result
38
        """
39
        result = []
40
        while left and right:
41
            result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
42
        result.extend(left)
43
        result.extend(right)
44
        return result
45

46
    if len(collection) <= 1:
47
        return collection
48
    mid_index = len(collection) // 2
49
    return merge(merge_sort(collection[:mid_index]), merge_sort(collection[mid_index:]))
50

51

52
if __name__ == "__main__":
53
    import doctest
54

55
    doctest.testmod()
56

57
    try:
58
        user_input = input("Enter numbers separated by a comma:\n").strip()
59
        unsorted = [int(item) for item in user_input.split(",")]
60
        sorted_list = merge_sort(unsorted)
61
        print(*sorted_list, sep=",")
62
    except ValueError:
63
        print("Invalid input. Please enter valid integers separated by commas.")
64