def merge(nums, left, mid, right):
    tmp = []
    i, j = left, mid + 1
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1

    while i <= mid:
        tmp.append(nums[i])
        i += 1

    while __________:
        tmp.append(nums[j])
        j += 1

    for k in range(len(tmp)):
        nums[left + k] = tmp[k]

def mergeSort(nums, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    mergeSort(nums, left, mid)
    mergeSort(nums, mid + 1, right)
    merge(nums, left, mid, right)

if __name__ == "__main__":
    nums = [3, 1, 4, 1, 5, 9, 2, 6]
    mergeSort(nums, 0, len(nums) - 1)
    print(nums)