Python实现Merge Sort时出现IndexError，求修正方法

你的代码存在两个核心问题，导致索引越界和排序失败：

1. Merge函数的索引逻辑错误 #

你用同一个变量i同时遍历左右两个数组，并且每次删除元素后还递增i。比如第一次循环删除left_array[0]后，left_array长度减1，此时i变成1，再访问left_array[i]就会直接越界。而且直接修改原数组（del操作）既低效又容易引发索引混乱，正确的做法是用两个独立指针跟踪两个数组的当前遍历位置，不修改原数组。

2. 递归调用未接收排序结果 #

merge_sort(right)和merge_sort(left)的递归排序结果没有赋值给原变量，导致你传入merge函数的始终是最初分割的未排序子数组，完全没用到递归排序后的结果。

修正后的完整代码 #

unsorted_list = [7, 4, 2, 1]

def merge(left_array, right_array):
    lst = []
    i = j = 0  # 用两个独立指针分别跟踪左右数组
    
    # 遍历两个数组，比较当前指针位置的元素
    while i < len(left_array) and j < len(right_array):
        if left_array[i] <= right_array[j]:
            lst.append(left_array[i])
            i += 1
        else:
            lst.append(right_array[j])
            j += 1
    
    # 追加剩余未遍历的元素
    lst.extend(left_array[i:])
    lst.extend(right_array[j:])
    
    return lst

def merge_sort(array):
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    
    # 接收递归排序后的子数组
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

print(merge_sort(unsorted_list))  # 输出: [1, 2, 4, 7]

关键修正点说明 #

• 用i和j两个独立指针分别遍历左右数组，避免索引混乱
• 用extend方法批量追加剩余元素，比循环更简洁高效
• 递归调用时接收排序后的子数组，确保传入merge的是已排序的左右部分

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