合并两个已升序列表出错，求修正方案（禁用sort()/sorted()）

需求要求 #

编写程序合并两个已按升序排序的列表，返回一个新的升序排序列表。需为每个列表维护当前索引以跟踪已处理的部分，原始列表不得修改。例如，若列表a为[1,4,9,16]，列表b为[4,7,9,9,11]，程序应返回新列表[1,4,4,7,9,9,9,11,16]，且禁止使用sort()和sorted()方法。

遇到的问题 #

我编写了如下代码，但输出结果为[1, 2, 3, 3, 6, 12, 11, 13, 14, 22, 17, 22, 23, 33]，未能正确排序。请问该如何修正？

def slistunion():
    a=[1,3,12,13,22,33]
    b=[2,3,6,11,14,17,22,23]
    print("list a is",a)
    print("list b is",b)
    l=[]
    shorter=min(len(a),len(b))
    longer= max(len(a),len(b))
    for i in range(0,shorter):
        l.append(a[i])
        l.append(b[i])
    lenghtdiff= len(b)-len(a)
    if lenghtdiff>0:
        lenghtdiff= len(a)-len(b)
    for i in range (lenghtdiff,0):
        l.append(b[i])
        a.append(a[i])
        z=0
    for i in range(0,len(l)-1):
        if l[i]>l[i+1]:
            a=l[i]
            l[i]=l[i+1]
            l[i+1]=a

你的代码存在几个核心问题：

• 合并逻辑错误：只是交替插入两个列表的元素，未对比元素大小按升序合并，直接导致列表无序。
• 剩余元素处理混乱：长度差计算和循环范围错误，还修改了原始列表a，违反“原始列表不得修改”的要求。
• 排序逻辑无效：仅做了一次相邻元素交换，不是完整的排序逻辑，无法让整个列表有序。

正确的思路是使用双指针法，分别跟踪两个列表的当前处理位置，每次选择较小的元素加入结果列表，直到其中一个列表处理完毕，再将另一个列表的剩余元素全部追加到结果中。

修正后的代码：

def slistunion():
    a = [1, 3, 12, 13, 22, 33]
    b = [2, 3, 6, 11, 14, 17, 22, 23]
    print("list a is", a)
    print("list b is", b)
    
    i = j = 0  # 双指针，分别对应a和b的当前索引
    merged = []
    
    # 同时遍历两个列表，每次选择较小的元素加入结果
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1
    
    # 处理a中剩余的元素
    while i < len(a):
        merged.append(a[i])
        i += 1
    
    # 处理b中剩余的元素
    while j < len(b):
        merged.append(b[j])
        j += 1
    
    print("merged list is", merged)
    return merged

slistunion()

代码说明 #

• 用i和j两个指针从两个列表的起始位置开始遍历，每次比较当前指针指向的元素，将较小的元素加入结果列表后移动对应指针。
• 当其中一个列表遍历完成后，直接将另一个列表的剩余元素追加到结果中——因为原列表本身是升序的，剩余元素必然大于结果中的所有元素。

这样处理后的列表自然是升序的，完全符合需求：未修改原始列表，用索引跟踪处理进度，也未使用任何内置排序方法。

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