merge.py

def merge_sort(arr):
    if len(arr) > 1:
        middle = len(arr) // 2

        left = arr[:middle]
        right = arr[middle:]

        merge_sort(left)
        merge_sort(right)

        merge(arr, left, right)


def merge(arr, left, right):
    i = 0
    j = 0
    k = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # if the condition for the loop above is false, consider the array to be sorted
    # copy the rest of the elements from left and right into arr
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        k += 1
        j += 1


arr = [23, -100, 3, 99, 45]
print(f"before merging : {arr}")
merge_sort(arr)
print(f"after merging: {arr}")