Python高效合并有序列表：heapq.merge实现O(N)算法

Python中高效合并两个（或多个）有序列表的正确姿势是使用`heapq.merge`——它充分利用输入已排序的特性，以严格的O(m+n)时间复杂度和O(1)额外空间完成归并，远胜于先拼接再排序的`sorted(a + b)`；它返回轻量惰性生成器，天然支持多路、异构有序输入（如元组、range、文件行），且具备健壮的边界处理与优化路径，但需注意所有输入必须同序、不可重复消费，并警惕类型混淆、字典序陷阱等常见误区——掌握它，能让你的归并操作既快又稳。

为什么不用 sorted(a + b)？

因为 sorted(a + b) 会先拼接再排序，时间复杂度是 O((m+n) log(m+n))，完全浪费了“两个列表本来有序”这个前提。而 heapq.merge 是专门为此类场景设计的——它不建堆、不排序，只做归并，本质是多路归并算法，时间复杂度严格 O(m+n)，空间上也只用 O(1) 额外空间（不计输出）。

heapq.merge 的基本用法和关键参数

它接受任意多个已排序的可迭代对象，返回一个惰性生成器（不是 list），按升序归并输出：

import heapq
a = [1, 3, 5]
b = [2, 4, 6, 7]
merged = heapq.merge(a, b)  # <generator object merge at 0x...>
list(merged)  # [1, 2, 3, 4, 5, 6, 7]

• 所有输入必须是**升序排列**的；降序需显式传 key 或反转逻辑
• 支持任意数量的输入： heapq.merge(a, b, c, d)
• 支持不同类型的可迭代对象：tuple、range、甚至文件行（只要有序）
• 不修改原列表，也不强制转为 list —— 如果你只需要遍历一次，直接 for 循环更省内存

常见错误：KeyError 或结果乱序

实际用时最容易踩的坑是类型/顺序不一致：

• 混入未排序数据：heapq.merge([3,1], [2,4]) → 结果是 [3,1,2,4]，不是错，但不符合预期
• 字符串比较陷阱：heapq.merge(['10', '2'], ['3']) → 按字典序得 ['10', '2', '3']，而非数值序；需用 key=int
• 传入 generator 且被多次消费：g = (x for x in [1,3]); list(heapq.merge(g, [2])) 第二次调用会空，因为 g 已耗尽
• key 参数必须一致：heapq.merge(a, b, key=lambda x: -x) 表示所有输入都按**降序逻辑**归并，不能 a 升序 b 降序

和手动双指针比，merge 有什么实际优势？

手写双指针当然也能做到 O(N)，但 heapq.merge 在真实工程中更稳：

• 天然支持 >2 路归并，手写容易出边界错
• 内部做了优化：对两路输入会走快速路径（跳过堆操作），性能接近手写
• 自动处理空输入、单元素、长度悬殊等情况，无需额外判空
• 与 itertools.chain、filter 等组合自然，比如：heapq.merge(filter(is_even, a), filter(is_even, b))

真正要注意的是：它返回生成器，如果你后续要多次索引或 len()，记得转成 list 或用 collections.deque(..., maxlen=0) 快速丢弃；否则可能因重复迭代导致逻辑异常。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Python高效合并有序列表：heapq.merge实现O(N)算法》文章吧，也可关注golang学习网公众号了解相关技术文章。