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)

ZGVmIG1lcmdlKGEsIGxlZnQsIG1pZGRsZSwgcmlnaHQpOgogICAgIiIiCiAgICBtaWRkbGUtLSDQv9C+0YHQu9C10LTQvdC40Lkg0Y3Qu9C10LzQtdC90YIg0L/QtdGA0LLQvtC5INGH0LDRgdGC0LgKICAgICIiIgogICAgdG1wID0gWzBdICogKHJpZ2h0ICsgMSAtIGxlZnQpCiAgICBwb3MxID0gbGVmdAogICAgcG9zMiA9IG1pZGRsZSArIDEKICAgIHBvczMgPSAwCiAgICB3aGlsZSBwb3MxIDw9IG1pZGRsZSBhbmQgcG9zMiA8PSByaWdodDoKICAgICAgICBpZiBhW3BvczFdIDw9IGFbcG9zMl06CiAgICAgICAgICAgIHRtcFtwb3MzXSA9IGFbcG9zMV0KICAgICAgICAgICAgcG9zMSArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgdG1wW3BvczNdID0gYVtwb3MyXQogICAgICAgICAgICBwb3MyICs9IDEKICAgICAgICBwb3MzICs9IDEKICAgIHdoaWxlIHBvczEgPD0gbWlkZGxlOgogICAgICAgIHRtcFtwb3MzXSA9IGFbcG9zMV0KICAgICAgICBwb3MxICs9IDEKICAgICAgICBwb3MzICs9IDEKICAgIHdoaWxlIHBvczIgPD0gcmlnaHQ6CiAgICAgICAgdG1wW3BvczNdID0gYVtwb3MyXQogICAgICAgIHBvczIgKz0gMQogICAgICAgIHBvczMgKz0gMQogICAgZm9yIGkgaW4gcmFuZ2UocG9zMyk6CiAgICAgICAgYVtsZWZ0ICsgaV0gPSB0bXBbaV0KCgpkZWYgbWVyZ2Vfc29ydChhLCBsZWZ0PTAsIHJpZ2h0PU5vbmUpOgogICAgIyAxCiAgICAjIGlmIHJpZ2h0ID09IC0yMjg6CiAgICAjICAgIHJpZ2h0ID0gbGVuKGEpIC0gMQogICAgIyAyCiAgICByaWdodCA9IHJpZ2h0IG9yIChsZW4oYSkgLSAxKQoKICAgIGlmIGxlZnQgPCByaWdodDoKICAgICAgICBtaWRkbGUgPSAobGVmdCArIHJpZ2h0KSAvLyAyCiAgICAgICAgbWVyZ2Vfc29ydChhLCBsZWZ0LCBtaWRkbGUpCiAgICAgICAgbWVyZ2Vfc29ydChhLCBtaWRkbGUgKyAxLCByaWdodCkKICAgICAgICBtZXJnZShhLCBsZWZ0LCBtaWRkbGUsIHJpZ2h0KQogICAgICAgIAoKQSA9IFs0LCAyLCA1LCAxLCAzXQpBX3NvcnRlZCA9IFsxLCAyLCAzLCA0LCA1XQptZXJnZV9zb3J0KEEpCnByaW50KEEp