归并排序Merge函数出现List index out of range错误求助

核心错误原因 #

初始化L = []和R = []为空列表后，Python不允许直接通过L[i]给指定索引赋值——空列表长度为0，任何索引都会超出有效范围，这就是触发List index out of range的直接原因。此外，代码的合并阶段也存在类似的索引错误，且未处理子数组遍历完后的剩余元素。

分步修复方案 #

1. 修复子数组赋值逻辑
   替换直接索引赋值为append()方法，或者预先初始化指定长度的列表：

   • 方案一（推荐）：用append()动态添加元素

     for i in range(n1):
         L.append(A[p+i])
     for i in range(n2):
         R.append(A[q+i])
     

   • 方案二：预先初始化列表长度

     L = [0] * n1
     for i in range(n1):
         L[i] = A[p+i]
     R = [0] * n2
     for i in range(n2):
         R[i] = A[q+i]
     

2. 修复合并阶段的逻辑缺陷
   原代码中Array = []为空列表，直接Array[x] = ...同样会触发索引越界，且未处理子数组剩余元素。正确的合并逻辑应直接修改原数组的对应区间，并补充剩余元素处理：

完整修正代码 #

A = [1,2,6,8,3,4,5,7]
# p = 0,r = 7 ,q = 3
def Merge(A,p,q,r):
    n1 = q - p
    n2 = r - q
    L = []
    R = []
    # 修复子数组赋值：用append添加元素
    for i in range(n1):
        L.append(A[p+i])
    for i in range(n2):
        R.append(A[q+i])
    i = 0
    j = 0
    k = p  # 指向原数组A的当前写入位置
    # 合并两个子数组到原数组A的[p..r]区间
    while i < n1 and j < n2:
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    # 处理L中剩余的未合并元素
    while i < n1:
        A[k] = L[i]
        i += 1
        k += 1
    # 处理R中剩余的未合并元素
    while j < n2:
        A[k] = R[j]
        j += 1
        k += 1

Merge(A,0,3,7)
print(A)  # 输出: [1,2,3,4,5,6,7,8]

关键修正点说明 #

• 用append()替代直接索引赋值，彻底解决空列表索引越界问题
• 合并时直接修改原数组的目标区间，符合归并排序的常规实现逻辑
• 添加两个while循环处理子数组遍历完后的剩余元素，确保所有元素都被正确合并
• 改用while循环处理合并逻辑，更灵活应对子数组长度不一致的边界情况

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