Python归并排序实现报错求助：IndexError索引越界问题

错误1：空列表直接赋值索引导致越界 #

你初始化arr1 = []和arr2 = []后，直接用arr1[i] = arr[s+i]赋值会触发索引越界错误——空列表没有对应的索引位置，Python不支持这种赋值方式。解决办法要么提前初始化列表的固定长度，要么用append()方法添加元素。

错误2：mergeSort调用的终止索引错误 #

原代码调用mergeSort(arr,0,len(arr))，但数组的最后一个有效索引是len(arr)-1，传入len(arr)会导致递归时处理超出数组范围的位置，引发后续逻辑错误。

修复后的代码 #

def mergeSort(arr, s, e):
    if s >= e:
        return
    mid = s + (e - s) // 2
    mergeSort(arr, s, mid)
    mergeSort(arr, mid + 1, e)
    merge(arr, s, mid, e)


def merge(arr, s, mid, e):
    # 提前初始化子数组长度，避免索引赋值错误
    n = mid - s + 1
    m = e - mid
    arr1 = [0] * n
    arr2 = [0] * m
    
    for i in range(n):
        arr1[i] = arr[s + i]
    for i in range(m):
        arr2[i] = arr[mid + i + 1]
    
    i = j = 0
    k = s
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            arr[k] = arr1[i]
            i += 1
        else:
            arr[k] = arr2[j]
            j += 1
        k += 1
    
    while i < len(arr1):
        arr[k] = arr1[i]
        i += 1
        k += 1
    
    while j < len(arr2):
        arr[k] = arr2[j]
        j += 1
        k += 1


arr = [1,5,0,3,-15,99,1500,-1500,66,120]
mergeSort(arr, 0, len(arr)-1)  # 修正终止索引为len(arr)-1
print(arr)

更Pythonic的写法参考 #

利用Python切片特性简化代码，省去手动填充子数组的循环：

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [1,5,0,3,-15,99,1500,-1500,66,120]
sorted_arr = mergeSort(arr)
print(sorted_arr)

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