合并两个有序数组：从暴力排序到双指针原地归并的保姆级教程

合并两个有序数组这道题，在 LeetCode 上挂着 Easy 的标签，但真到了面试现场，它能淘汰的人远比想象中多。我印象很深，有一次候选人把“先合并再排序”写出来，然后理直气壮说这就是最优解，我追问了一句“那如果 nums1 空间刚好只够呢”，他愣了好一会儿。这个题目表面上是考数组操作，本质上考的是双指针思维、原地操作的边界处理，以及对时间复杂度的敏感度。今天我就把这题掰开揉碎，从最暴力的做法讲到面试官最喜欢的原地双指针，顺便把 Python 里那些能偷懒的内置工具也拿出来遛一遛。

这篇文章不是单纯给你背答案，而是把每种解法背后的“为什么”讲清楚。无论你是准备面试的算法新手，还是写业务代码时想优雅地合并两个有序列表，都能拿到可以直接抄作业的方案，以及我在实际调试中踩过的那些坑。

1. 先搞清楚题目在问什么

1.1 题目描述和隐藏陷阱

原题长这样：给定两个有序整数数组 nums1 和 nums2，把 nums2 合并到 nums1 中，使最终结果仍然有序。这里有个关键约束，nums1 的长度是 m + n，前 m 个位置放的是有效元素，后面 n 个位置用 0 占位，专门腾出来给 nums2 的元素用。

这个“末尾补 0 占位”的设计是第一个陷阱。很多第一次做这道题的人，一看是“合并”，直接写nums1.sort()，结果把末尾的 0 全排到前面去了。我见过不止一个人在这里翻车，而且翻车之后还一脸茫然，觉得 Python 的 sort 出了问题。

第二个陷阱藏在“原地”这两个字里。题目要求把结果直接写进 nums1，不允许你 new 一个全新的数组返回。这意味着你的解法必须考虑到 nums1 的容量是固定的，你不能在中途让 nums1 的长度随意变化，更不能用nums1 = nums1 + nums2这种重新赋值的招数——这会让 nums1 指向一个全新的对象，并不是真正原地修改。

1.2 面试官到底想考什么

别看这题标着 Easy，它一次性考了三个重要的算法基本功。

第一个是双指针技术。两个有序数组合并，本质上是把两个升序序列归并成一个升序序列，这是归并排序的 merge 阶段。归并排序是分治思想的核心代表，如果你连 merge 都不会写，后面遇到链表归并排序、外部排序、多路归并，基本就卡死了。

第二个是边界条件处理。m 和 n 可能为 0，数组可能很长，元素可能全是重复的。这些边界情况在面试中就是送分题，也是送命题。很多人主流程写得飞快，一遇到空数组就报 IndexError，这种失误在面试官眼里是很掉价的。

第三个是空间复杂度优化。从“新建数组再合并”到“从后往前原地合并”，空间复杂度从 O(m) 降到 O(1)。面试官追问“能不能不申请额外空间”的时候，考的就是你有没有意识到从后往前操作可以避免覆盖问题。

1.3 这题的通用价值比想象中大

我在实际工作中，被这个 merge 逻辑救过好几次。比如两个渠道各拉了一份用户列表，都按注册时间排好序了，要合并成一个去重后的列表用于全量推送；再比如日志系统中多个分片的日志文件要按时间戳合并成一个大文件，这就是典型的 merge 过程。还有数据库做归并连接（Merge Join）的时候，本质上也是这种有序序列合并的扩展。

所以说，花时间把这题吃透，不只是为了过面试，它本身就是一个在工程里高频出现的基础操作。你把这题的边界情况和优化思路搞明白了，后面遇到各种“合并有序”相关的问题，都等于白捡。

2. 方案一：先合并再排序，最直观但也最容易被追问

2.1 代码确实能一行搞定

先来看最简单的写法：

def merge(nums1, m, nums2, n): nums1[m:] = nums2 nums1.sort()

如果你只是要一个能跑的答案，那就到这里为止了。nums1[m:] = nums2是把 nums2 的所有元素覆盖到 nums1 从第 m 位开始的区间上，也就是把那些占位的 0 替换成真正的数据。然后sort()把整个数组重新排序。

这个解法能通过，但隐藏了一个你必须要知道的细节：nums1[m:] = nums2是在原地修改 nums1 的切片，所以赋值的长度不需要和原切片长度一样，列表会自动调整大小。如果你的 nums1 长度恰好是 m + n，那么这个操作不会改变列表长度，正好满足题目要求。

2.2 为什么这种解法在面试里会被追问

时间复杂度是 O((m+n) log(m+n))，因为sort()是基于 Timsort 的，最坏情况下需要这么多时间。空间复杂度取决于 sort 的具体实现，Timsort 在最坏情况下会申请 O(n) 的额外空间，虽然是 C 语言层面的内存，不算我们代码里的显式空间，但面试官较真的话，这也能算一笔账。

最关键的问题在于，这个解法完全没有利用“两个数组已经各自有序”这个前提。你等于把两个有序数组先打乱成一个大杂烩，再重新排序。理想情况下，合并两个有序数组只需要一趟线性扫描，时间复杂度是 O(m+n)，而你却用了一个 log 级别的排序，这在数据量大的时候差距非常明显。

举几个数字体感一下：当 m=1000、n=1000 时，O(m+n) 只需要大约 2000 次比较，而 O((m+n)log(m+n)) 需要 2000 * 11 等于 22000 次比较，差了一个数量级。当数据量到了十万级别，差距会更吓人。

2.3 什么时候可以放心用

如果面试官明确说“我不要求最优解，你先把能跑的写出来”，那先写这个方案是完全没问题的，至少能证明你基本功扎实。但写完一定要主动说：“这个方法时间复杂度是 O((m+n)log(m+n))，没有利用数组有序的性质，我可以优化到 O(m+n)。” 这句话一出口，面试官基本就放心了。

在工作里，如果合并的两个列表都不大，比如总量几百条，我也会偷懒用 sort 方案，毕竟代码可读性最高，维护成本最低。性能优化要分场景，不是任何地方都值得上最优解。

3. 方案二：双指针法，这道题的标准答案

3.1 核心思想就是“谁小谁先走”

双指针的思路非常朴素：你面前有两排从小到大排列的士兵，现在要把他们合并成一排，你只需要两个手指头，分别指在两排的第一个士兵身上。每次比较两个手指指向的士兵，谁个子矮谁就先站到新队伍里，然后让那排的指针往后挪一位。重复这个过程，直到其中一排空了，再把另一排剩下的人全部接上去。

这个比喻涵盖了双指针解法的全部核心逻辑：比较当前两个指针指向的元素，把较小的放进结果数组，然后移动对应指针。循环结束条件是两个指针中有任何一个越界，最后做一次收尾，把另一个数组剩余的元素全部拷进去。

3.2 从前往后合并，需要 O(m) 额外空间

最容易想到的双指针版本是创建一个新数组来存结果，但题目要求原地修改 nums1，不能返回新数组，所以这里有个折中策略：先把 nums1 的有效部分复制一份出来，然后在这份副本和 nums2 上进行双指针比较，把结果写回 nums1。

def merge(nums1, m, nums2, n): nums1_copy = nums1[:m] i, j, k = 0, 0, 0 while i < m and j < n: if nums1_copy[i] <= nums2[j]: nums1[k] = nums1_copy[i] i += 1 else: nums1[k] = nums2[j] j += 1 k += 1 while i < m: nums1[k] = nums1_copy[i] i += 1 k += 1 while j < n: nums1[k] = nums2[j] j += 1 k += 1

这里有个细节值得停下来想一下：为什么要把 nums1 的有效部分先复制出去？因为题目要求原地写回 nums1，而 nums1 的前 m 个位置正在被我们当作结果区域使用。如果直接用 nums1 的前面部分来存结果，当你从前面拿走一个 nums1 的元素时，那个位置的原始值就被覆盖了，后面还没被比较的 nums1 元素就丢了。复制副本的本质是用 O(m) 的空间换取不被覆盖的安全性。

这段代码的时间复杂度是 O(m+n)，空间复杂度 O(m)。作为双指针入门，它比后面的原地版本更容易理解，尤其适合第一次接触归并思想的人。

3.3 从后往前合并，面试官最想看到的版本

如果面试官追问“能不能不用额外空间”，答案就是从后往前填。既然 nums1 后面有 n 个空位，那我们就从最后一个位置开始往前写，每次都取两个数组当前剩余元素中的较大者，放到结果数组的末尾。这样可以保证已经写进去的元素不会覆盖掉还没读取的 nums1 元素。

def merge(nums1, m, nums2, n): p1 = m - 1 p2 = n - 1 p = m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 nums1[:p2 + 1] = nums2[:p2 + 1]

最后一行是很多人容易漏掉的关键：如果 nums2 还有剩余元素，直接把 nums2 开头的那些元素覆盖到 nums1 开头。为什么？因为 nums1 开头的元素要么已经被正确地放到后面去了，要么就是和 nums2 剩余元素比较后留下的较大值，此时 nums1 开头的空闲位置正好放 nums2 剩下的较小值。这个收尾操作的时间复杂度是 O(1) 的量级（切片赋值按位置逐个写入，实际是 O(p2+1)），但确实把代码的边界处理补全了。

如果反过来，nums1 还有剩余元素，就不需要特殊处理了，因为它们本来就在 nums1 前面的位置，而且是这一轮比较中的较小值，留在原地就是正确的。很多人第一次写在这里会犯迷糊，要么多写一个 while p1 >= 0 的循环，要么不知道怎么处理 p2。多写一个循环也不算错，只是不够简洁。

3.4 两种双指针方案怎么选

从前往后版本需要 O(m) 额外空间，从后往前版本是 O(1) 额外空间，两者时间复杂度都是 O(m+n)。面试的时候，我的建议是先把从前往后版本的思路讲清楚，让面试官看到你理解了双指针的核心逻辑，再主动补充一句“其实还可以从后往前，把空间复杂度降到 O(1)”，然后直接写出原地版本。

写的时候还要注意一个比较运算符的细节：在内层 if 判断里，用>还是>=会影响相同元素的来源顺序。用>则当 nums1[p1] 和 nums2[p2] 相等时，取 nums2 的元素，等于把相同元素的相对顺序颠倒了；用>=才会让考验相对顺序的合并保持稳定。严谨的工程场景下，稳定性很重要，但面试时更关键的是你要意识到这个问题存在，并且能说出你选某个符号的理由。

4. 方案三：Python 内置工具，到底能不能用

4.1 heapq.merge 合并迭代器

Python 的 heapq 模块里藏着一个 merge 函数，专门用来合并多个有序序列。它的效果和双指针 merge 一致，但返回的是一个迭代器，非常省内存。

from heapq import merge def merge_with_heapq(nums1, m, nums2, n): nums1[:] = list(merge(nums1[:m], nums2))

这行代码的步骤是：先取 nums1 前 m 个元素作为迭代器，和 nums2 一起传给 merge，得到一个新的迭代器，然后转成列表，用切片赋值的方式写回 nums1。

必须说明的是，merge内部用的是堆结构，一次只从两个迭代器里取元素，空间占用很小，但当你list()把它消耗完时，内存占用就是 O(m+n)。所以从空间复杂度看，它和直接新建数组没有本质区别。另外，切片赋值nums1[:]要求右边序列长度和 nums1 长度一致，否则会改变列表长度，在这个题目场景里正好一致，所以能用。如果 nums1 长度不是 m+n 而是更多，这个写法还需要调整为nums1[:m+n] = ...。

这个方案我一般只在工程里合并两个迭代器流时用，面试时不推荐当作主答案，因为面试官大概率没听过 heapq.merge，你还得解释一堆，不如从后往前双指针来得干净。

4.2 bisect.insort 逐个插入

如果你要合并的数组不太长，也可以用二分查找定位插入点，然后逐一把 nums2 的元素插进 nums1：

import bisect def merge_with_insort(nums1, m, nums2, n): nums1[:] = nums1[:m] for x in nums2: bisect.insort(nums1, x)

这里先把 nums1 的前 m 个有效元素单独提出来，因为不处理掉的话，后面的 0 也会参与二分查找，插入位置会错。然后每进来一个元素，insort 会找到它应该插入的下标，并把后续元素整体后移。

这个方案的时间复杂度是 O(n * m)，因为每次插入都是 O(m) 的线性移动，n 个元素就是 O(n*m)。数组规模小，比如两个长度都不到 100，用起来完全没问题，代码简洁，可读性很高。但面试时千万别拿这个当最优解，会被追问到怀疑人生。

4.3 用 Timsort 的特性能不能偷懒

前面说过，直接nums1[m:] = nums2; nums1.sort()是 O((m+n)log(m+n))。但因为 Python 的 sort 是 Timsort，它专门优化了“部分有序”的情况，所以当两个子数组都是有序的时，实际运行时间可能会接近 O(m+n)。理论上最坏复杂度还是 O((m+n)log(m+n))，但如果你只用一句“实测很快”来论证，在面试里站不住脚。

不过有意思的是，Timsort 的有序性检测确实能识别出“前半段有序、后半段有序”的结构。我在本地用长度为 10000 的两个随机有序数组测试过，nums1[m:] = nums2; nums1.sort()和双指针原地 merge 的耗时差距在十几毫秒的量级，感知不强。但在面试里，你要跟面试官讲清楚的是理论复杂度，而不是跑个 benchmark 来抬杠。

4.4 方案选择建议

如果让我给一个直接的结论：

• 工程里，数据量小且追求可读性，直接用nums1[m:] = nums2; nums1.sort()。
• 工程里，数据量较大但内存充足，用heapq.merge或者自己写的双指针版本。
• 面试里，第一反应写双指针，追问空间复杂度时写从后往前版本。
• 如果面试官不排斥你用内置库，也可以提一句 heapq.merge，作为加分项展示你对标准库的熟悉程度。

5. 变式题目和真实场景扩展

5.1 合并 K 个有序数组

面试中这道题经常被扩展成：现在有 K 个有序数组，怎么合并成一个有序数组？你的第一反应可能是两两合并，但合并 K 次的复杂度是 O(K * N)，因为每合并一次数据规模都在变大。更优的做法是使用最小堆，先把每个数组的第一个元素放进堆里，然后每次弹出最小值，再从这个最小值所在数组的下一个位置取元素入堆。这样总时间复杂度是 O(N log K)，堆的大小始终是 K。

这在工程上就是经典的“多路归并”，搜索引擎索引构建、大数据排序的外部归并阶段都在用这个思路。如果你面试时能把这道题从两路扩展到 K 路，顺带讲清楚堆的作用，面试官对你这题的印象分直接拉满。

5.2 合并后找中位数

另一个热门变式是 LeetCode 第 4 题：两个有序数组合并后的中位数。你要是真把两个数组合并再找中位数，复杂度是 O(m+n)，虽然能过，但最优解要求 O(log(min(m,n)))。做法是利用二分查找，在两个数组的交错位置上找到一个切分点，使得左半部分的最大值小于右半部分的最小值。这个思路更考验对有序数组性质和二分查找的理解，也是从“合并有序数组”延伸出来的经典进阶题。

如果你刚把这题的基础版吃透，我建议顺手刷一下第 4 题。它们共享同一个直觉：有序数组的归并、切分和中位数本质上是同一个主题下的不同问法。

5.3 真实工程：日志合并与用户列表合并

说回实际工作。有一次我做数据迁移，要从两张历史表里导用户 ID，两张表都按 ID 递增排好序，目的是合并成一个文件给下游去重后全量处理。数据量大概是千万级别，用 SQL 里的UNION等于是先合再排序，数据库压力大得吓人。我直接用双指针合并两个有序文件流，一边读一边写，内存占用稳定在几 MB，跑完大概十分钟。那次经历让我对 merge 这个操作的实用价值印象极深。

另一个场景是日志系统。每个服务节点会生成局部有序的日志文件，需要按时间戳合并成全局有序的日志流做问题排查。这种场景你不可能把所有日志都读进内存再排序，必须用迭代器或者流式 merge，按行读取，比较时间戳，决定先输出哪一条。这就是heapq.merge的实际用武之地。

5.4 稳定排序和相等元素处理的思考

最后补充一个容易忽略的点：合并有序序列时的稳定性。所谓稳定，是指两个数组中如果出现相等的元素，合并后它们的前后顺序是否和原数组一致。

如果你在两个相等的元素之间倾向于保留 nums1 的元素在前，那在用<=比较时需要小心。从前往后版本中，if nums1_copy[i] <= nums2[j]会让 nums1 的相等元素先被取走；如果写<，就是 nums2 的相等元素先被取走。两种写法都不影响结果数组的有序性，但面试官如果问到“合并过程会不会破坏相对顺序”，你能意识到这个差异并给出选择理由，会显得你考虑得很周全。

6. 常见问题与避坑技巧实录

6.1 高频报错和排查思路

我在各种各样的教程群、内推群里看到过很多人贴自己写的合并有序数组代码，出问题的地方高度一致。我把最常见的几类整理成一张表，方便你对照排查。

6.2 边界条件逐条过一遍

不管是自己写还是看别人代码，我都会习惯性把下面这些边界条件在心里过一遍：

• m = 0，说明 nums1 没有有效元素，合并结果等于 nums2。从前往后版本会直接跳过第一个 while，进入 nums2 的收尾循环；从后往前版本会直接执行nums1[:p2+1] = nums2[:p2+1]。
• n = 0，说明 nums2 是空数组，结果等于 nums1 原本的样子。两个版本都会跳过第二轮逻辑，代码不会报错。
• m = 0 且 n = 0，两个数组都是空的，合并结果还是空数组，需要保证代码此时不越界。
• nums1 和 nums2 全部相等，此时双指针会一直走 else 分支或者 if 分支，取决于比较符号，最终结果依然有序。
• nums1 的有效元素全部小于 nums2，从后往前版本中 p2 走完后，nums1 开头要覆盖的恰好是 nums2 的全部，结果正确。
• nums2 的所有元素都小于 nums1 的有效元素，从后往前版本中 p1 走完后，nums2 剩余元素直接放到 nums1 最前面，可以做到完全不额外申请内存。

6.3 独家经验心得

这里分享几个我反复踩过之后才养成的习惯。

第一，写双指针时永远先确定指针的含义。p1、p2、p 分别指什么，初始值是什么，循环条件是什么，三个问题写下来贴在自己面前，再动代码。很多错误都源于指针含义模糊。

第二，从后往前的版本中，最后一行的切片赋值nums1[:p2 + 1] = nums2[:p2 + 1]经常被忽略。我发现把这个写反成nums1[:p1 + 1] = nums1[:p1 + 1]的人也有，那等于什么都没做。一定要理解：只有 nums2 剩余元素需要特殊处理，nums1 剩余元素本来就在正确位置。

第三，用切片比较顺手但也会藏问题。nums1[:m]是复制出一个新列表，不会影响原来的 nums1，这是对的。但如果你写tmp = nums1，那不是复制，只是给同一个列表起了个别名，后面tmp被修改时，nums1 也会跟着变，很多人第一次写代码就在这里莫名奇妙地丢数据。

第四，检查代码时不要只盯着主循环，也要把收尾循环和极端输入都跑一遍。有时候主循环写得完美，结果收尾循环少写了k += 1或者下标写错，一调试就是半天。

最后说个心态层面的东西。合并两个有序数组这道题，看起来简单，但它是很多算法思维的起点。你把它彻底吃透，后面学归并排序、二分查找、堆、K 路归并，都会有“原来还是这套东西”的豁然开朗感。别嫌这题简单，能把简单题讲清楚、写干净、边界考虑全，本身就比会背一堆模板的人强得多。

我自己后来面试别人的时候，也特别喜欢拿这题当开场。不是因为想刁难人，而是从一道 easy 题里，就能看出一个人是背了答案还是真正理解了算法。你写代码前有没有先和面试官确认输入输出的含义，你写完后会不会主动补边界用例，你在被追问空间复杂度时是直接懵掉还是快速切换思路，这些才是这题真正的价值所在。