如何合并两个不同长度的预排序列表并保持有序？

需求：将两个不同长度的预排序列表合并为一个有序列表，要求基于现有代码修改，不能使用heap、sort、merge、zip、字典等内置方法，目标结果为 new_list = [0, 1, 1, 3, 5, 5, 9, 9, 9]。

现有问题：当前代码会遗漏其中一个列表的剩余元素（比如示例中numbers2末尾的9），直接将循环条件的and改为or会出现索引越界问题。

原代码：

def sort_numbers(list1, list2):
    new_list = []
    list1_index = 0
    list2_index = 0

    while list1_index != len(list1) and list2_index != len(list2):
        if list1[list1_index] < list2[list2_index]:
            new_list.append(list1[list1_index])
            list1_index += 1
        else:
            new_list.append(list2[list2_index])
            list2_index += 1
    return new_list


def main():
    numbers1 = [1, 3, 5, 5]
    numbers2 = [0, 1, 9, 9, 9]
    sorted_numbers = sort_numbers(numbers1, numbers2)
    print(sorted_numbers)


if __name__ == "__main__":
    main()

问题分析 #

原循环仅在两个列表都有未遍历元素时执行，当其中一个列表遍历完成后，循环直接终止，导致另一个列表中剩余的有序元素无法加入结果列表。若直接将and改为or，当某一索引超出列表长度时，访问对应列表元素会触发索引越界错误。

修改方案 #

在原循环结束后，分别检查两个列表是否还有剩余元素，将剩余的有序元素直接追加到结果列表中：

修改后的代码：

def sort_numbers(list1, list2):
    new_list = []
    list1_index = 0
    list2_index = 0

    while list1_index != len(list1) and list2_index != len(list2):
        if list1[list1_index] < list2[list2_index]:
            new_list.append(list1[list1_index])
            list1_index += 1
        else:
            new_list.append(list2[list2_index])
            list2_index += 1
    
    # 追加list1中剩余的元素
    while list1_index != len(list1):
        new_list.append(list1[list1_index])
        list1_index += 1
    
    # 追加list2中剩余的元素
    while list2_index != len(list2):
        new_list.append(list2[list2_index])
        list2_index += 1
    
    return new_list


def main():
    numbers1 = [1, 3, 5, 5]
    numbers2 = [0, 1, 9, 9, 9]
    sorted_numbers = sort_numbers(numbers1, numbers2)
    print(sorted_numbers)  # 输出: [0, 1, 1, 3, 5, 5, 9, 9, 9]


if __name__ == "__main__":
    main()

说明 #

1. 保留原循环逻辑，处理两个列表都有未遍历元素的场景，逐个比较并加入较小的元素。
2. 原循环结束后，通过两个独立的while循环处理剩余元素——因为原列表是预排序的，剩余元素本身保持有序，直接追加即可保证结果列表的有序性。

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