def merge_sort(arr, left, right):
if left >= right:
return
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
def merge(arr, left, mid, right):
temp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
temp.extend(arr[i:mid+1])
temp.extend(arr[j:right+1])
for k in range(len(temp)):
arr[left + k] = temp[k]