不使用内置函数排序两个列表 修复代码IndexError索引越界错误

报错原因 #

出现IndexError索引越界的核心问题是合并阶段的逻辑存在多处缺陷：

• 内层循环遍历范围错误：初始时value为list_b的长度，range(value+1)会让j最大取值到value，但列表索引是从0开始的，list_b的最大合法索引为len(list_b)-1，本身就存在越界风险。
• 动态修改列表后未适配索引：循环过程中调用list_b.remove()会让list_b的长度不断缩短，但j还是按初始设定的范围遍历，当j超过当前list_b的最大合法索引时，访问list_b[j]就会直接抛出索引越界错误。
• 逻辑不完整：就算解决索引问题，当前合并逻辑既没有把list_a的元素加入结果，也没有把遍历完list_a后list_b剩余的元素补入结果，最终返回的列表是不全的。

正确实现方案 #

要求不使用内置排序函数的前提下，保留原有正确的插入排序逻辑，合并阶段改用有序数组合并的标准双指针方案即可：

def merge(list_a, list_b):
    # 对第一个列表做插入排序
    for i in range(1, len(list_a)):
        current = list_a[i]
        j = i
        while j > 0 and list_a[j-1] > current:
            list_a[j] = list_a[j-1]
            j -= 1
        list_a[j] = current
    
    # 对第二个列表做插入排序
    for i in range(1, len(list_b)):
        current = list_b[i]
        j = i
        while j > 0 and list_b[j-1] > current:
            list_b[j] = list_b[j-1]
            j -= 1
        list_b[j] = current
    
    # 双指针合并两个有序列表
    i = j = 0
    resultant = []
    len_a, len_b = len(list_a), len(list_b)
    # 同时遍历两个列表，每次取更小的元素加入结果
    while i < len_a and j < len_b:
        if list_a[i] <= list_b[j]:
            resultant.append(list_a[i])
            i += 1
        else:
            resultant.append(list_b[j])
            j += 1
    # 把未遍历完的列表剩余元素追加到结果末尾
    resultant.extend(list_a[i:])
    resultant.extend(list_b[j:])
    return resultant

调用测试用例print(merge([1, 4, 5, 7, 9], [2, 3, 6, 8, 10]))，会正确输出[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。

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