Python作业：无排序函数合并不同长度已排序列表的优化及归并算法解析

问题说明 #

这是一项Python作业：要求实现一个merge函数，能被主函数调用，将两个已预排序的列表合并成单个有序列表。规则是：

• 禁止使用sort()或类似内置排序方法
• 不建议自定义排序算法
• 函数要适配任意长度的输入列表和随机数值

现有代码能通过自动评分，但存在潜在问题，需要更优实现；同时需要理解真正的归并排序算法及其O(nlogN)时间复杂度。

现有代码的问题 #

先看用户的实现：

def merge(number1, number2):
    mlist = []
    i = 0
    j = 0
    while i < len(number1) and j < len(number2):
        if number1[i] < number2[j]:
            mlist.append(number1[i])
            i = i + 1
        elif number2[j] < number1[i]:
            mlist.append(number2[j])
            j = j + 1
    x = mlist[-1] + 1
    if len(number2) > len(number1):
        y = number2.index(x)
        mlist.extend(number2[y:])
    elif len(number1) > len(number2):
        y = number1.index(x)
        mlist.extend(number1[y:])
    return mlist

这段代码有两个明显问题：

1. 遗漏相等元素：当number1[i] == number2[j]时，两个分支都不触发，会导致这两个元素都被跳过，最终结果缺失数据。
2. 索引查找的潜在报错：用mlist[-1]+1作为查找值，如果剩余列表中不存在这个值，index()会直接抛出ValueError，比如合并[1,3,5]和[2,4,7]时，循环结束后mlist是[1,2,3,4,5]，x=6，number2.index(6)会报错。

优化后的merge实现 #

标准的双指针写法就能解决这些问题，逻辑更简洁且无bug：

def merge(number1, number2):
    mlist = []
    i = j = 0
    len1, len2 = len(number1), len(number2)
    
    # 双指针遍历两个列表，逐个取较小元素
    while i < len1 and j < len2:
        if number1[i] <= number2[j]:
            mlist.append(number1[i])
            i += 1
        else:
            mlist.append(number2[j])
            j += 1
    
    # 直接追加剩余元素（剩余部分本身就是有序的，无需额外查找）
    mlist.extend(number1[i:])
    mlist.extend(number2[j:])
    
    return mlist

优化点：

• 用<=处理相等元素，避免遗漏
• 遍历结束后直接追加剩余列表的未遍历部分，因为两个输入都是预排序的，剩余元素必然大于等于mlist中的所有元素，无需额外查找索引
• 提前缓存列表长度，避免重复计算len()

归并排序算法解析 #

你提到的归并排序，核心是分治法，流程如下：

1. 拆分：把一个未排序的列表不断拆分成两个子列表，直到每个子列表只有1个元素（单个元素默认有序）
2. 合并：用上述的merge函数，把相邻的有序子列表两两合并，最终得到完整的有序列表

时间复杂度O(nlogN)的解释 #

• 拆分阶段：n个元素的列表，每次拆成两半，需要拆分的层数是log2(n)（比如8个元素拆3层：8→4→2→1），这就是复杂度中logN的来源
• 合并阶段：每一层合并的总操作数都是O(n)（因为每一层的所有子列表加起来总长度是n）
• 总时间复杂度就是层数 × 每层操作数 = O(nlogN)

测试验证 #

用你提供的测试代码验证优化后的函数：
测试示例代码：

number1 = [0, 2, 3]
number2 = [1, 4, 5, 6, 9]
retlist = merge(number1, number2)
print(retlist)  # 输出: [0,1,2,3,4,5,6,9]

自动测试代码（包含随机用例）：

import random

def test_main_2():
    n1 = [random.randint(0, 20) for i in range(5)]
    n2 = [random.randint(0, 20) for i in range(3)]
    n1.sort()
    n2.sort()
    tlist = n1 + n2
    tlist.sort()
    print('Test data')
    print(n1)
    print(n2)
    retlist = merge(n1, n2)
    print('After merge', retlist)
    print('Expected', tlist)
    assert tlist == retlist

test_main_2()

运行后会自动验证合并结果是否和预期一致，且不会触发任何报错。

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