两个数组合并排序全解析：从双指针归并到原地合并与去重

前阵子做日志归并工具遇到了一个看似简单、却把我折腾得不轻的问题两个数组合并排序。A 数组是用户行为日志B 数组是系统事件日志各路日志内部都按时间戳排好了序我需要把它们合并成一条完整的事件流同时保证顺序稳定。起初我图省事直接数组拼接再统一排序测试数据量不大跑起来没什么感觉等接上真实数据几十万条日志堆进来处理时间一下涨了几十倍这才意识到“两个数组合并排序”这几个字背后藏着不少值得较真的细节。这篇文章不仅写给准备面试的开发者后端处理日志归并、前端合并多接口列表数据、做数据清洗的同事应该都能用得上。我会把几种常见的合并排序场景拆开配合代码、复杂度分析和踩坑记录讲清楚什么情况下用什么方案而不是一味地“管他呢先排序再说”。1. 先别急着写代码把“合并排序”的需求拆出四种完全不同的场景我见过太多人写这类代码之前根本没想过输入数据的性质。同样是“两个数组合并排序”需求差别可以很大A、B 本来就是两个有序数组还是一个乱序数组、一个有序数组输出要求是新数组还是允许直接在原数组上操作合并之后要不要去重这四个问题的答案直接决定了你该选哪套算法。我在这里先给出一个分类后面每一类展开来讲拼接后整体排序对原数组是否有序没有要求把两个数组合并后统一排序输出新数组。有序数组合并输入本身就是有序的输出也要求有序但允许新建一个数组。原地合并题目或业务要求不能开新数组把 B 合并进 AA 已经预留了足够空间。合并并去重在合并排序的基础上去掉重复元素重复的定义和顺序保留规则也各有要求。用一个表格来对照一下这几种场景的特征会非常直观场景输入是否有序是否可以开新数组是否去重最优复杂度拼接后整体排序不要求均可可选O((mn)log(mn))有序数组合并必须有序可以否O(mn)原地合并必须有序否否O(mn)空间 O(1)合并并去重视情况可以是有序时可 O(mn)这个表看起来简单但它帮我在实际项目里节省了大量无谓的优化。有次某同事让我帮忙看一个合并逻辑为什么这么慢我一看代码输入是已经从数据库按时间排好序的两个分页结果他却用拼接后 sort 的方式做数据量一到百万级别几乎每秒都在白白浪费排序比较。问题根源不在于“排序函数不够快”而在于没有利用输入本身已经有序这个前提。很多人一看到“合并排序”就条件反射去想快排、归并排序怎么实现但工程问题从来不是比谁背的算法多而是比谁更会在动手前识别场景。你把场景认对了最优方案往往自己就浮出来了场景认错了代码再漂亮也是浪费资源。2. 一把梭的concat加sort能跑但你必须知道它隐藏在背后的三个坑先把最简单、也最容易被当成“标准答案”的方案摆出来。Python 里很多人会直接这样写def merge_and_sort(a, b): return sorted(a b)JavaScript 里是这样const merged [...arr1, ...arr2].sort((a, b) a - b);Java 里相对啰嗦一点一般是先把两个数组转成列表合并再调用 Collections.sort或者直接用 Streamint[] result IntStream.concat(Arrays.stream(a), Arrays.stream(b)) .sorted() .toArray();这个方案的优点是代码量少、可读性好如果只是几十上百条数据完全够用。但它有三个坑我一个个说。2.1 坑一默认 sort 是按字符串排序不是按数值排序JavaScript 的 sort 如果不传比较函数是按 UTF-16 编码转成字符串后逐个比较的。这意味着 [1, 2, 10].sort() 的结果会是 [1, 10, 2]因为字符串 10 排在 2 前面。很多新手在这里翻车数据正好跨过 10 这个坎排序结果就错了。所以 JS 里必须显式传比较函数sort((a, b) a - b)。而 Python 的 sorted 对数字会按数值大小排序没有这个问题。但如果数组里混了数字和字符串Python 会直接抛 TypeError这倒不一定坏事至少不会悄悄给出错误结果。我排查过的前端 bug 里真有不少 “数字排序错乱” 的案例最后定位都是 sort 没传比较函数。这个问题太基础了以至于老手也容易想当然地以为默认排序就按数值大小来。2.2 坑二复杂度的量级不划算拼接一个新数组需要 O(mn) 的时间和空间来复制所有元素排序一个长度为 mn 的数组时间复杂度是 O((mn)log(mn))。问题是如果两个输入数组本身就有序你完全可以利用这个信息把时间压到 O(mn)。差距有多大呢假设 mn 是一百万log2(1000000) 约等于 20那么直接排序要做大约两千万次比较归并只需要大约一百万次比较。虽然现代语言的内置排序做过大量优化实际差距没有数学上那么大但在数据量大的工程场景里慢上几倍很正常。我当时在日志工具中遇到的延迟就是这种差距的真实体现。2.3 坑三稳定性这个隐藏属性可能决定业务是否正确稳定排序的意思是值相等的元素排序前后相对顺序保持不变。Python 的 Timsort 是稳定的ES2019 之后也要求 JavaScript 的 sort 必须稳定。默认情况下直接排序倒是没什么问题但如果你塞进了复杂的比较逻辑比如时间相同再按来源优先级排序排序器内部的交换次数和结果可能与你预期不一致。更隐蔽的问题是当你把比较器写得“很聪明”时比如根据某个外部状态甚至异步函数来决定大小这种比较器不仅破坏了排序算法的稳定性还会导致结果不可预测性能也会直线下降。我的建议是排序之前先把需要比大小的字段算成一个确定值再用简单比较函数做排序别想着在比较器里秀花活。3. 双指针归并两个有序数组合并排序时的最优解如果题目明确告诉你两个数组各自有序那最佳选择就是双指针归并。这个思路同时也是归并排序的核心面试常考工程上也用得最多。3.1 思路拆解从“两摞有序扑克牌”说起把两个有序数组想成两堆已经按从小到大叠好的扑克牌。你每次只需要看两堆牌顶部的牌把较小的那张抽出来放进结果里然后继续比较新的牌顶。因为有序列信息在“全局最小”一定出现在两个牌顶之一不需要每次都翻遍整堆牌。对应到数组上就是两个指针 i 和 j 分别指向 A、B 的当前位置比较 A[i] 和 B[j]谁小就把谁写进结果数组指针后移。重复到某个指针走到头为止再把另一个数组剩下的部分整体拷进来。3.2 代码实现def merge_sorted(a, b): i j 0 m, n len(a), len(b) result [] while i m and j n: if a[i] b[j]: result.append(a[i]) i 1 else: result.append(b[j]) j 1 if i m: result.extend(a[i:]) if j n: result.extend(b[j:]) return result注意比较时用的是 而不是 。这样当 A 和 B 里有相等元素时优先取 A 的元素结果数组中 A 的元素会排在 B 的相等元素之前保证排序稳定的语义。如果你在业务里需要“以 A 数组的时间戳相同时优先保留 A 的来源记录”这个细节很关键。时间复杂度 O(mn)原因是每个元素最多被比较一次、被移动一次空间复杂度 O(mn)主要花在存结果上。如果不需要稳定可以在比较时用 效果一样但语义不同。3.3 什么时候值得用什么时候没必要很多文章把双指针吹成“最优解”但我要补一句前提只有当输入数组已经有序时双指针才能做到 O(mn)。如果两个数组本来就没有排序信息可以利用那你做的所有“归并”操作本质上只是在复制元素最后仍然需要整体排序复杂度跟直接 sort 没区别。另外如果数组长度加起来只有几个元素双指针代码反而显得啰嗦直接 sort 更清爽。我写工具类代码时会先加一个阈值判断比如 len(a) len(b) 64 就直接拼接排序否则走归并。这个阈值纯属个人习惯但确实能避免小数据量上的过度设计。3.4 顺带一提归并排序就是反复做这件事如果你正在准备面试看到“归并排序”四个字本质就是把一个数组不断拆成两半分别排好序之后再用这个 merge 逻辑合并起来。很多人背归并排序的代码背不下来其实就是没有把 merge 这个子过程吃透。先把本文这段 merge_sorted 写得滚瓜烂熟归并排序的 merge 步骤你就已经会了一半。4. 原地合并倒着遍历把“覆盖风险”变成“顺理成章”还有一种高频场景不允许开新数组要求把 B 合并进 A并且 A 的尾部已经预留了足够空间。很多刷题的同学第一次看到这类题都会懵因为在正面比较时很容易覆盖还没处理的元素。我的经验是把方向反过来想问题就迎刃而解。4.1 为什么正着走会出事假设 A [1, 2, 3, 0, 0, 0]m 3代表有效元素是前三个B [2, 5, 6]n 3A 的末尾三个空位留给合并结果。如果从前往后做双指针比较到某个时刻你可能把 A 中还没参与比较的元素写掉。比如 A[1] 2 放在前面但 A[2] 3 如果还没被读走一个新值写进 A[2] 就会丢失 3。尽管这类题目的标准做法可以开一个临时数组再写回但那样就等于没用上“原地”的意义。4.2 倒着写的思路和实现从前往后是“谁小谁先走”那从后往前就是“谁大谁先放”。A 的有效区从 m-1 倒着走B 从 n-1 倒着走结果位置从 mn-1 倒着写。因为两个数组的尾部是空的大的元素从后面填入永远不会碰到还没处理的小元素。def merge_inplace(nums1, m, nums2, n): i, j, p m - 1, n - 1, m n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[p] nums1[i] i - 1 else: nums1[p] nums2[j] j - 1 p - 1循环条件是 j 0不是 i 0。为什么因为 A 的有效元素已经存在于 nums1 里如果 B 的元素先被搬完A 剩下的元素本来就在最终位置附近不需要再动但如果 i 先走到头说明剩余需要写入的全是 B 的元素循环会继续把 B 的内容填完。两个数组都走到头时p 恰好等于 -1算法结束。空间复杂度 O(1)时间 O(mn)这是这类题目的最优解。当年我面试时第一次看到这个思路有种“窗户纸被捅破”的感觉原来只要倒着写覆盖问题就根本不存在了。4.3 一个容易踩的变体m 可能是 0如果 A 原本没有有效元素m 0此时 i 初始为 -1循环里 i 0 永远不会成立等价于把 B 的每个元素从后往前原样写入 nums1。很多人会漏掉这个 case结果程序直接越界。写的时候要时刻记住判 i 的时候先看 i 0顺序不能反。5. 合并还要去重三种做法按场景选“两个数组合并排序”经常会附带另一个需求去重。去重的写法也分好几档不能一上来就无脑用 Set。5.1 无脑方案Set 加排序def merge_unique_sorted(a, b): return sorted(set(a) | set(b))这行代码最省事对输入是否有序没要求也能去重输出天然有序。代价是 set 在内存占用上比较高当数组元素是大对象或者数量很大时尤其明显。此外 set 本身是无序的如果你希望保留原数组中的首次出现顺序set 完全帮不上忙。5.2 有序数组上的双指针去重合并如果两个输入数组已经有序又想省内存、利用有序性可以在双指针归并的基础上加一个去重条件写入结果时只有当当前元素和 result 最后一个元素不等时才 append。def merge_unique_sorted_inplace(a, b): i j 0 m, n len(a), len(b) result [] while i m or j n: if j n or (i m and a[i] b[j]): candidate a[i] i 1 else: candidate b[j] j 1 if not result or result[-1] ! candidate: result.append(candidate) return result这段代码把“取较小值”和“去重”合在一个循环里复杂度仍是 O(mn)。注意候选值的来源判断必须处理好某一方已经耗尽的情况否则会越界。这里的套路和第 3 章的双指针很像只是多了一行 result[-1] ! candidate 的判断。5.3 无序数组还要保顺序用 seen 集合如果输入无序要求合并后去重且保留元素第一次出现的顺序最优方案不是排序而是遍历时记录已经见过的元素def merge_unique_keep_order(a, b): seen set() result [] for x in a b: if x not in seen: seen.add(x) result.append(x) return result这种写法时间复杂度 O(mn)但这里的顺序是“原数组里的出现顺序”不是排序顺序。如果既要保顺序又要排序那就只能先排序再做双指针去重或者老老实实 sort 后再去重两个目标无法同时无代价满足。三种方案可以拿下面这个表格对比方案输入要求复杂度输出特征set 加 sorted无O(mn) 时间额外空间较大有序且去重不保证原序双指针去重合并有序O(mn)低额外空间有序且去重稳定seen 保序去重无序O(mn) 时间O(mn) 空间保原顺序不一定有序我实际项目里去除重复日志时更常用双指针版本因为日志本身按时间有序用 set 反而会打乱时间线的顺序性后续还要再排序白白多一轮开销。6. 测试用例与翻车现场边界条件才是稳不稳的关键算法写得再漂亮边界测不稳照样上线翻车。我把这些年实际踩过的坑整理成了一份测试清单建议你直接拿来当参考。6.1 空数组是最容易忽视的 case两个数组都为空返回空。A 为空、B 非空返回 B 的副本。双指针实现如果漏掉循环结束后的剩余元素复制结果就会丢数据。我之前在双指针函数里只写了 while i m and j n后面没有任何复制剩余数组的逻辑遇到空数组时结果少一截这个 bug 当时查了整整一个下午。6.2 两个数组内容完全相同比如 A [1,2,3]B [1,2,3]。双指针归并用 时会先取完 A 的所有元素再把 B 的相同元素依次放入结果是 [1,1,2,2,3,3]。如果你希望合并后去重那这里正好是个典型用例如果你不希望去重这个结果也没问题只是别惊讶为什么相同元素会相邻出现。6.3 负数、浮点数、NaN整数测试跑通了不代表浮点没问题。几个坑Python 的 sorted 对 NaN 的排序行为不稳定因为 NaN 与任何值比较都不成立。JavaScript 的 sort 比较函数 (a, b) a - b 遇到 NaN 时返回 NaN引擎会把 NaN 解释为 0导致结果顺序完全看容器心情很难预测。负数排序本身没有特殊问题但如果你用了字符串拼接再排序的方式“-2” 和 “-10” 的字典序就乱套了。解决办法是在真正进入排序算法之前先把数组里的非法值、类型不统一的元素过滤或规整掉。宁可多一行清洗代码也不要让排序函数去猜。6.4 长度悬殊的两个数组A 有 100 万条B 只有 1 条。双指针里 B 的元素可能在第一次比较就被写进去也可能一直排到很后面这都没问题。但如果你优化时自作聪明地写了个“先把短数组拼到长数组末尾再整体排序”结果往往比双指针慢很多。遇到这种场景双指针的 O(mn) 优势体现得淋漓尽致。6.5 一个简易的测试矩阵用例输入期望输出容易踩的 bug全空([], [])[]忘记处理空数组A空([], [1,2])[1,2]剩余未复制B空([1,2], [])[1,2]剩余未复制单元素([3], [1])[1,3]比较方向写反重复([1,1], [1,2])[1,1,1,2] 或去重后 [1,2]去重逻辑错乱全同([2,2], [2,2])[2,2,2,2]用 导致不稳定负数和零([-3, -1], [-2, 0])[-3,-2,-1,0]字典序排序错误长数组悬殊([1..100000], [999999])双指针结果正确简单 sort 慢我自己在写工具前都会先写一个这样的用例列表跑完再上真实数据。别嫌麻烦这种基础逻辑如果出 bug线上排查的难度远高于你当初省下的五分钟。7. 从面试题到工程实战哪些业务会真用到这些操作聊到这里可能有同学会问这玩意儿除了面试实际工作里真的会用吗我可以负责任地说会而且相当频繁。7.1 日志归并多来源日志按时间合并我做日志归并工具时遇到的就是这个场景。多个服务会把各自带有时间戳的日志写到不同的文件或队列里每一路日志自身基本有序但全局想合并成一条时间线就必须不断取出各路日志里时间最早的记录本质上就是多路归并。两个数组合并排序是最简单的两路版本扩展到 k 路就是把两路归并反复嵌套或者用一个最小堆维护 k 个当前值。当时我第一版用拼接再排序数据量上来后日志事件流明显延迟。换成双指针归并后同一批数据的处理时间从几十秒降到几百毫秒级别对比非常直观。这个优化思路至今都还在支撑着我后来写的日志分析工具。7.2 分页结果合并数据库或接口层的常见操作分库分表之后各分片的查询结果分别按某个字段排序应用层想要“把这几个分片的结果合并成一条有序分页数据”。如果直接合并后重新排序内存占用和排序时间都会成倍增长更聪明的做法是只取各分片前 k 条做归并然后截取需要的页。k 通常比总数小很多能省不少资源。面试里也常见一个变体两个有序数组找合并后的第 k 个元素。这题不一定需要把整个数组合并出来可以用二分每次淘汰 k/2 个元素把复杂度压到 O(logk)。如果你理解了双指针的原理这个变体理解起来会顺畅很多。7.3 前端列表合并注意 sort 的坑前端拿到的多份列表往往来自不同接口合并展示时最容易踩的坑就是 JavaScript 的 sort 默认字典序问题。我之前在某系统里见过一个 bug列表数字排序后 10 出现在 2 前面排查半天发现没人传比较函数。所以你在前端写合并排序时第一件事就是确认 arr.sort() 后面跟着的是不是 (a, b) a - b。另外数据量很大且需要虚拟滚动时前端同样值得用双指针归并而不是把所有数据拉下来拼完再排。尤其是用户翻页时一次性拼接所有数据会让首屏渲染变慢分批归并能明显改善体验。7.4 外部排序把内存装不下的数据排好序文件太大时操作系统一次性读不进内存这时候需要外部排序。通用做法是把大文件切成多个可以放进内存的块每一块分别排序后写入临时文件最后反复做多路归并。这里的两两归并就是双指针归并在文件流上的体现。理解了“两个数组合并排序”的最简模型外部排序对你来说也只是把内存数组换成文件句柄而已。实际工作中我不必天天手工写这些基础算法很多语言和框架已经封装好了。但了解背后的复杂度与边界条件不是为了炫技而是在出现性能问题或诡异 bug 时能一眼定位根源。做了这么多年工程最大的体会是像“两个数组合并排序”这种看似基础的问题恰恰是性能优化和隐蔽 bug 的高发区。我个人的习惯是真正动手前先问四件事输入是否有序、能不能开新数组、要不要去重、是否必须稳定。这四个答案基本决定了我该选哪套方案省掉了无数次返工。如果你也在维护类似的合并逻辑不妨按这个思路把现有代码捋一遍说不定就能找到我当初那样让耗时下降几个数量级的优化点。