def merge(a, left, middle, right):
    """
    middle-- последний элемент первой части
    """
    tmp = [0] * (right + 1 - left)
    pos1 = left
    pos2 = middle + 1
    pos3 = 0
    while pos1 <= middle and pos2 <= right:
        if a[pos1] <= a[pos2]:
            tmp[pos3] = a[pos1]
            pos1 += 1
        else:
            tmp[pos3] = a[pos2]
            pos2 += 1
        pos3 += 1
    while pos1 <= middle:
        tmp[pos3] = a[pos1]
        pos1 += 1
        pos3 += 1
    while pos2 <= right:
        tmp[pos3] = a[pos2]
        pos2 += 1
        pos3 += 1
    for i in range(pos3):
        a[left + i] = tmp[i]


def merge_sort(a, left=0, right=None):
    # 1
    # if right == -228:
    #    right = len(a) - 1
    # 2
    right = right or (len(a) - 1)

    if left < right:
        middle = (left + right) // 2
        merge_sort(a, left, middle)
        merge_sort(a, middle + 1, right)
        merge(a, left, middle, right)
        

A = [4, 2, 5, 1, 3]
A_sorted = [1, 2, 3, 4, 5]
merge_sort(A)
print(A)