Python归并排序（Merge Sort）出现IndexError（列表索引越界）求助

嘿，刚接触Python就敢上手归并排序处理2000条数据，已经超棒啦！遇到IndexError索引越界的问题别慌，咱们一步步拆解原因，搞定它～

归并排序里的索引越界，大多出在递归分割逻辑或者合并子数组的循环里，再加上读取文件时可能的异常数据，也会间接引发问题：

• 递归终止条件没写对：比如没判断子数组长度是否小于等于1，导致递归分割空数组
• 合并时的指针边界错误：比如用了i <= len(left)而不是i < len(left)，导致指针超出列表范围
• 读取文件时没处理异常行：比如空白行、格式错误的行，生成的列表里有无效元素，打乱了排序逻辑

1. 先确保读取的记录是有效的 #

先检查你读取文件的代码，有没有跳过空白行、处理格式异常的内容？比如你的文件里可能有行是空的，或者格式不是xxx 数字的样子，这些都会导致生成的列表有问题。

可以先加个小检查：读取完文件后，打印一下列表的长度，看看是不是和预期的2000条接近，再随机看几个元素是否正常：

records = []
with open('your_file.txt', 'r') as f:
    for line in f:
        line = line.strip()
        if not line:
            continue  # 跳过空白行
        # 这里根据你的格式解析数据，比如提取名字和分数
        records.append(line)
print(f"有效记录数：{len(records)}")
print(records[:5])  # 看前5条是否正常

2. 检查归并排序的核心逻辑 #

给你一个不会触发索引越界的归并排序实现，你可以对比自己的代码找差异：

正确的归并排序实现（按分数排序为例） #

假设我们把每条记录解析成(分数, 名字)的元组，方便排序：

def merge_sort(arr):
    # 递归终止条件：子数组长度<=1时直接返回
    if len(arr) <= 1:
        return arr
    # 分割数组，mid用整数除法避免浮点数
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # 合并两个有序子数组
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    # 循环条件是指针都在各自子数组范围内
    while i < len(left) and j < len(right):
        # 按分数升序排序，你也可以改成按名字排序
        if left[i][0] <= right[j][0]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # 把剩余的元素直接追加进去，不用再循环，避免索引错误
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

关键修复点 #

• 递归终止条件明确：len(arr) <=1，不会继续分割空数组或单元素数组
• 合并时用i < len(left)和j < len(right)作为循环边界，绝对不会越界
• 剩余元素用extend直接添加，代替手动循环，减少出错概率

3. 完整的运行示例 #

把读取文件、排序、写入结果整合起来：

def read_records(file_path):
    records = []
    with open(file_path, 'r', encoding='utf-8') as f:
        for line in f:
            line = line.strip()
            if not line:
                continue
            # 解析你的格式：比如"afsdgf(name) 34(marks)"
            parts = line.split()
            try:
                # 提取分数，去掉(marks)后缀
                marks = int(parts[-1].replace('(marks)', ''))
                # 提取名字，去掉(name)后缀
                name = ' '.join(parts[:-1]).replace('(name)', '')
                records.append( (marks, name) )
            except (ValueError, IndexError):
                print(f"跳过格式错误的行：{line}")
    return records

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

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

if __name__ == "__main__":
    # 替换成你的文件路径
    records = read_records('student_records.txt')
    print(f"共读取到 {len(records)} 条有效记录")
    # 排序
    sorted_records = merge_sort(records)
    # 写入排序后的文件
    with open('sorted_student_records.txt', 'w', encoding='utf-8') as f:
        for marks, name in sorted_records:
            f.write(f"{name}(name) {marks}(marks)\n")
    print("排序完成，结果已写入文件！")

如果你的代码和上面的差异不大，那大概率是读取文件时没处理异常行，导致列表里有无效元素，或者递归时的mid计算用了普通除法（比如(low+high)/2）得到了浮点数，分割数组时出错。

你可以先跑上面的示例代码，看看能不能正常运行，再对比自己的代码找问题～

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