Python高效归并排序实现异常：merge函数问题求助

1. 调用merge_sort时的右边界错误 #

你传入的数组[1, 5, 4, 2, 33, 4, 2, 44, 22, 0]共有10个元素，有效索引范围是0~9，但你调用时传的r=10超出了数组的最大索引，导致后续切片和元素访问逻辑出错。正确调用应为：

print(merge_sort([1, 5, 4, 2, 33, 4, 2, 44, 22, 0], 0, 9))

2. merge函数的参数传递不匹配 #

在merge_sort中，你将数组划分为左半段l~m、右半段m+1~r，但调用merge时传入的第三个参数是m。而merge函数中用arr[l:m]表示左半部分（Python切片为左闭右开，对应索引l~m-1），这直接导致左半段丢失了索引m的元素。

修复方法是将merge的调用参数改为m+1，确保左半段切片arr[l:m+1]覆盖l~m的所有元素：

def merge_sort(arr, l, r):
    if r > l:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m+1, r)
        return merge(arr, l, m+1, r)  # 此处将m替换为m+1

修复后的完整代码 #

def merge(arr, l, m, r):
    merged_arr = []
    i, j = 0, 0
    # 用长度计算替代重复切片，提升效率
    left_length = m - l
    right_length = r - m + 1
    while i < left_length and j < right_length:
        if arr[l+i] < arr[m+j]:
            merged_arr.append(arr[l+i])
            i += 1
        else:
            merged_arr.append(arr[m+j])
            j += 1
    # 拼接剩余未处理的元素
    merged_arr.extend(arr[m+j:r+1])
    merged_arr.extend(arr[l+i:m])
    arr[l:r+1] = merged_arr
    return

def merge_sort(arr, l, r):
    if r > l:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m+1, r)
        return merge(arr, l, m+1, r)

# 测试验证
test_array = [1, 5, 4, 2, 33, 4, 2, 44, 22, 0]
merge_sort(test_array, 0, 9)
print(test_array)  # 输出：[0, 1, 2, 2, 4, 4, 5, 22, 33, 44]

内容的提问来源于stack exchange，提问作者Gerry