Python:在不使用内置排序的情况下组合两个排序列表(并保持它们排序)

Question

我在网上找到了这个合并排序解决方案，我想知道 while 循环是否可行，或者是否还有使用 2 个 for 循环并比较它们的方法。

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    print result

合并([1,2,6,7], [1,3,5,9])

Answer 1

Python 的内置 sorted 实际上在这方面非常有效(因为它使用的 TimSort 利用了列表子集中的现有排序)。也就是说，有一个内置功能甚至可以避免构建新的 list ，例如 sorted (或您的解决方案)将:heapq.merge

它专为您拥有每个独立排序的现有列表的场景而设计。它是一个生成器函数，因此根本不需要创建新的 list。如果您尝试这样做是为了学习，请尽情享受，但如果这是针对“真实”代码，请使用随附的电池并避免重新发明轮子。