merge_sort.py

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)
        merge(arr,left,right)

def merge(arr, left, right):
    i = 0
    j = 0
    max_i, max_j = len(left), len(right)
    for index in range(len(arr)):
        if left[i] <= right[j]:
            arr[index] = left[i]
            i += 1
            if i == max_i:
                arr[index+1:] = right[j:]
                break
        else:
            arr[index] = right[j]
            j += 1
            if j == max_j:
                arr[index+1:] = left[i:]
                break
        index += 1