Untitled

def merge(arr, lf, mid, rg):
    array_left = [arr[i] for i in range(lf, mid)]
    array_right = [arr[i] for i in range(mid, rg)]
    array_merged = list()
    i = j = 0
    while i < len(array_left) and j < len(array_right):
        if array_left[i] <= array_right[j]:
            array_merged.append(array_left[i])
            i += 1
        else:
            array_merged.append(array_right[j])
            j += 1
    while i < len(array_left):
        array_merged.append(array_left[i])
        i += 1
    while j < len(array_right):
        array_merged.append(array_right[j])
        j += 1
    return array_merged


def merge_sort(arr, lf, rg):
    if rg - lf <= 1:
        return
    mid = (lf + rg) // 2
    merge_sort(arr, lf, mid)
    merge_sort(arr, mid, rg)
    arr[lf: rg] = merge(arr, lf, mid, rg)


def test():
    a = [1, 4, 9, 2, 10, 11]
    b = merge(a, 0, 3, 6)
    expected = [1, 2, 4, 9, 10, 11]
    assert b == expected
    c = [1, 4, 2, 10, 1, 2]
    merge_sort(c, 0, 6)
    expected = [1, 1, 2, 2, 4, 10]
    assert c == expected


if __name__ == '__main__':
    test()