python - 将两个排序列表合并为一个更大的排序列表

Question

我正在尝试制作一个合并函数，该函数将用于我正在制作的合并排序。

我遇到了一些麻烦，我似乎找不到错误。

我评论它是为了向你们展示我的思考过程:

def merge(aList, bList):
    newList = []
    while (len(aList) > 0) & (len(bList) > 0):  #Loop until both lists are empty
        if aList[0] < bList[0]:         #If the first item of aList is smaller than the first item of bList
            newList.append(aList[0])    #add that item to the new list
            aList.pop(0)                #and remove it from the original list

        else:                           #If it gets here, that means the first item of bList was smaller
            newList.append(bList[0])    #So put the first item of bList is the new list
            bList.pop(0)                #and remove it from the original
    return newList

list1 = [3, 4, 8, 9]
list2 = [1, 2, 5, 8]

print(merge(list1, list2))
print(list1)
print(list2)

输出:

[1, 2, 3, 4, 5, 8]
[8, 9]
[0]

我原以为 list1 和 list2 是空的，但由于某种原因，list1 中似乎有一个未放置的 8 和 9。有人有想法吗？

Answer 1

这是一个使用 Python 库的版本 heapq :

import heapq

def merge(aList, bList)
    return list(heapq.merge(aList, bList))