原地归并排序python实现

以下是原地归并排序的Python实现：

def merge(arr, lo, mid, hi):
    i = lo
    j = mid + 1
    aux = arr.copy()
    for k in range(lo, hi + 1):
        if i > mid:
            arr[k] = aux[j]
            j += 1
        elif j > hi:
            arr[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            arr[k] = aux[j]
            j += 1
        else:
            arr[k] = aux[i]
            i += 1

def sort(arr, lo, hi):
    if hi <= lo:
        return
    mid = lo + (hi - lo) // 2
    sort(arr, lo, mid)
    sort(arr, mid + 1, hi)
    merge(arr, lo, mid, hi)

def merge_sort(arr):
    sort(arr, 0, len(arr) - 1)
    return arr

其中，`merge`函数用于将两个有序的子数组合并成一个有序的数组，`sort`函数用于递归地将数组分成两半并排序，`merge_sort`函数是对外暴露的接口，用于调用`sort`函数并返回排序后的数组。