1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def merge(left_lst, right_lst):
    merged = []
    while left_lst or right_lst:
        if not left_lst:
            merged.extend(right_lst)
            return merged
        elif not right_lst:
            merged.extend(left_lst)
            return merged
        elif left_lst[0] <= right_lst[0]:
            merged.append(left_lst.pop(0))
        else:
            merged.append(right_lst.pop(0))
    return merged


def mergesort(lst):
    if len(lst) < 2:
        return lst
    else:
        mid = len(lst) // 2
        left_sorted = mergesort(lst[:mid])
        right_sorted = mergesort(lst[mid:])
        return merge(left_sorted, right_sorted)


if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"Before sorting:\n{values}")
    values = mergesort(values)
    print(f"After sorting:\n{values}")
    
    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"Before sorting:\n{values}")
    values = mergesort(values)
    print(f"After sorting:\n{values}")