python - 合并和排序列表：复杂性

Question

我正在编写代码以返回一个列表，该列表是其他两个排序列表的排序合并。该练习要求复杂度为 O(n+m)，其中 n 和 m 是要合并的两个列表中的元素。我解决了这个练习，认为复杂性是正确的，但我不确定，我可以请你看一下吗？

def merge1(a,b):
    last=-1
    saved=[]
    while a!=[] and b!=[]:
        current_max=max(a[last], b[last])
        saved.append(current_max)
        if current_max==a[-1]:
            a.pop()
        else:
            b.pop()

直到这里，复杂性肯定是正确的，我不确定以下

    if a==[]:
        for el in range(len(b)):
            saved.append(max(b))
            b.pop()
    else:
        for el in range(len(a)):
            saved.append(max(a))
            a.pop()
    saved.reverse()
    return saved

if我想可以只使用各种方法并避免最后一个循环来降低复杂性for，但是您能否给我您对我的代码的看法？谢谢各位。

标签： pythonsortingmergecomplexity-theory