合并两个有序列表 — 迭代双指针

你有两条已按升序排好的整数列表 a 和 b,需要合并成一条同样升序的列表,包含两边所有元素。实现 solution(a, b) -> list[int],采用 迭代双指针归并:在两条列表上各放一根指针,输出较小的值,前进对应指针,重复进行。当一边耗尽时,把另一边剩下的尾巴整段接到输出后。总开销为 O(n + m) 时间、O(n + m) 输出空间——不需要再排序,也不需要额外缓冲区。

相等情形要 稳定 处理:当 a[i] == b[j] 时先取 a(用 <=,不是 <)。这保证 a 中原本的元素在与 b 中相等键值元素混排时仍排在前面——本函数嵌进归并排序时、或一边代表主流、另一边代表次流且要求"次流后于主流"时,这一点不可缺。

举例:solution([1, 3, 5], [2, 4, 6]) 返回 [1, 2, 3, 4, 5, 6];solution([], [7, 8, 9]) 返回 [7, 8, 9];solution([2, 2], [2, 2]) 返回 [2, 2, 2, 2](四份都保留,且来自 a 的两份排在前面)。

实践背景

双指针归并是自底向上归并排序的核心步骤:把长度为 1 的有序段两两合并成长度 2 的段,再合并成长度 4、8,直到整段排好。所有外部排序算法本质上都是反复调用这个同一段代码——数据库排序内存装不下的 TB 级数据时靠的就是它。在交易场景里,这段代码用来把两个不同场所的 有序成交流 合并成一条统一的时间线,作为下游处理的前置:行情处理器 A 和 B 各自输出按时间戳排序的成交,合并后的"统一行情带"就是用一次线性归并搭出来的。稳定性在这里同样有意义——如果两个场所在同一微秒上都报了一笔,业内惯例通常是"主场在前",而这恰好就是 <= 相等处理所编码的语义。相对于递归形式,迭代形式可以避免在某条输入列表很长时撞上调用栈深度的问题。