“两个数组合并排序”这六个字可能是很多新手的第一个“噩梦”也可能是某个深夜加班的最后一根稻草。面试的时候它叫“合并两个有序数组”工作中它叫“归并两个数据源”考试的时候它叫“利用归并排序的思想”——名字换了一堆核心永远都是同一个。这篇文章我用从业者的视角把这个最简单的算法题拆到骨头里。你不仅能拿到可直接抄走的代码更能理解每一步操作背后的“为什么”学会在不同语言、不同场景下怎么灵活变通。无论是准备面试、应付考试还是写业务代码时遇到数据合并看完这篇你都能心里有底。1. 两个数组合并排序问题本质与场景拆解1.1 先说清楚问题本身题目可以描述成一句话给你两个数组把它们合并成一个数组并且保证结果是升序或者降序排列。这里有个容易被忽略的细节——题目描述里往往藏着“有序”两个字。比如“给你两个已经排好序的数组”甚至有的题目直接写“两个有序数组”。有没有这两个字解法完全不同。先看具体例子数组A [1, 3, 5, 7] 数组B [2, 4, 6, 8] 合并排序后 [1, 2, 3, 4, 5, 6, 7, 8]这个结果看起来平平无奇但它是“归并排序”这个重要算法的最基础单元。归并排序为什么能在各种排序算法里稳坐头部梯队靠的就是它。整个归并排序可以形象地理解为先把数组切成零碎小块再不停地“两两合并”每次合并都保证结果有序最后整体有序。除了面试和算法竞赛这种操作在真实业务里也到处都是。比如数据库里两个表的记录有序合并本质就是两个有序数组的归并。外部排序处理放不下内存的大文件时把磁盘上的多个有序临时文件合并成一个有序大文件一样是这个套路。后端服务从多个数据源各取一批增量数据拿到手后合并去重再统一处理底层也是这一套。说白了只要涉及“多个有序集合拼成一个有序集合”都跑不掉这个方法。1.2 有序和无序两个世界的解法咱们先分清楚两种情况因为很多人一上来就用错方法。第一个情况两个数组无序。比如A [5, 1, 4]B [3, 2]。这种最简单粗暴的做法是先把两个数组合成一个新数组然后对整个新数组做一次排序。C语言里可以用qsortJavaScript里直接concat再sortPython里再sort()。时间复杂度取决于你用的排序算法一般是O((nm)log(nm))。第二个情况两个数组各自有序。题目只要稍微加“有序”两个字就意味着你可以把效率提升到O(nm)——这是质的飞跃。因为两个数组都已经有序你不需要重新全局排序只需要用“双指针”一路比对、一路合并就行每个元素只被扫描一次高效得可怕。很多人在这一点上犯糊涂明明“合并后排序”这种办法写起来更简单为什么非要学复杂的双指针答案就藏在大数据量里。假设你有两个各含100万条记录的数组O((nm)log(nm)) 和 O(nm) 的差距会被拉到数倍甚至数十倍。在实际的业务场景里这个差距直接决定接口是50毫秒返回还是3秒超时。所以核心问题永远是**给你的数组是不是有序的**搞清楚前提才能选对工具。2. 双指针归并排序合并的核心算法2.1 双指针思路的直观理解双指针的思路用一句话概括就是两个数组各自站一个指针谁小谁先进结果数组然后对应的指针往前走一步直到一边先走完另一边全倒进去。生活化类比两摞按身高排好的扑克牌桌面上摆好最终区。每次只看两摞最上面的那张牌把较小的那张取走放到结果区。谁小了取谁取完露出下一张继续比。最后某摞空了直接把另一摞剩下的牌依次放进去收工。不追求绝对严谨的情况下这个流程可以用下面这段C语言代码描述void merge(int a[], int aLen, int b[], int bLen, int result[]) { int i 0, j 0, k 0; // 两个指针都没走到头就继续比 while (i aLen j bLen) { if (a[i] b[j]) { result[k] a[i]; } else { result[k] b[j]; } } // 把a里剩下的元素接上 while (i aLen) { result[k] a[i]; } // 把b里剩下的元素接上 while (j bLen) { result[k] b[j]; } }这段代码是所有后续变体的地基。你不需要背它你需要理解它背后的运行轨迹。我建议你拿一张纸把两个数组写下来然后用手指当指针一步步模拟一遍比看任何讲解都管用。2.2 为什么是O(nm)复杂度背后的直觉从代码能看出来每轮while循环里要么i往前走一步要么j往前走一步要么就进入某个数组的收尾循环。整个过程中数组A的每个元素被访问一次数组B的每个元素被访问一次共访问nm次所以时间复杂度是O(nm)。空间复杂度要看你把结果放哪。如果开了额外数组来存结果空间复杂度是O(nm)如果允许直接原地利用数组的尾部空位空间复杂度可以降到O(1)。这部分后面专门说。有必要单独强调一下“稳定”这个概念。归并过程里当两个元素相等时我们选择先取A的值这意味着相等的元素仍然能保持它们在原数组中的相对顺序这种排序算法叫“稳定排序”。比如排序对象是对象数组先按时间排序再按ID稳定排序那最终ID相同的记录仍然保持时间顺序这个特性在很多业务里非常有用。3. 多种语言实现对照与选择建议3.1 JavaScript不要无脑concat加sortJavaScript里新手最常见的写法是这样的function mergeArrays(arr1, arr2) { return arr1.concat(arr2).sort((a, b) a - b); }代码没错结果也对。问题在于sort底层通常是快排复杂度是O((nm)log(nm))数据量小的时候完全没感觉数据量上了几十万之后就开始心跳加速。如果两个数组本身是有序的双指针写法是更好的选择function mergeSorted(arr1, arr2) { const result []; let i 0, j 0; while (i arr1.length j arr2.length) { if (arr1[i] arr2[j]) { result.push(arr1[i]); } else { result.push(arr2[j]); } } while (i arr1.length) result.push(arr1[i]); while (j arr2.length) result.push(arr2[j]); return result; }推荐指数上小数据量几十条无脑concat sort完全没问题但既然你追求的是“掌握核心方法”建议直接记住双指针版本。顺便提一句JavaScript里还有个TypedArray相关的set方法适合处理二进制数据流的合并但那属于特殊场景不展开。3.2 Python切片、heapq、双指针三选一Python新手最自然的写法merged sorted(a b)。只要数据规模可控这完全没问题。但如果你处理的是大规模有序流式数据Python标准库heapq提供了更优雅的工具——heapq.merge。它接收多个有序可迭代对象返回一个合并后的迭代器内存友好适合处理无法一次性载入内存的数据。import heapq a [1, 3, 5] b [2, 4, 6] merged list(heapq.merge(a, b))不过heapq.merge处理大量有序序列时的底层逻辑本质还是堆排序和多路归并的结合它比单纯双指针更灵活之处在于能同时合并多个序列。手写双指针版本则是基础功def merge(a, b): i j 0 result [] while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]) i 1 else: result.append(b[j]) j 1 result.extend(a[i:]) result.extend(b[j:]) return result3.3 Java与C面试手撕代码的常用战场Java的Arrays.sort干不了“两路有序直接合并”的活它只会全量排序所以面试时手写归并是逃不掉的。Java版本无非是把C的指针换成下标写法几乎一模一样public int[] merge(int[] nums1, int m, int[] nums2, int n) { int[] result new int[m n]; int i 0, j 0, k 0; while (i m j n) { result[k] nums1[i] nums2[j] ? nums1[i] : nums2[j]; } while (i m) result[k] nums1[i]; while (j n) result[k] nums2[j]; return result; }这里我还想提一个极具代表性的面试题变体——LeetCode 88题“合并两个有序数组”。它要求在nums1里原地合并不允许返回新数组两个数组的有效长度是m和n但nums1的长度是mn后面已经预留了空位。很多人在原地合并时从头开始操作结果把nums1还没处理的元素覆盖了。正确做法是从后往前填充public void merge(int[] nums1, int m, int[] nums2, int n) { int i m - 1; int j n - 1; int k m n - 1; while (i 0 j 0) { if (nums1[i] nums2[j]) { nums1[k--] nums1[i--]; } else { nums1[k--] nums2[j--]; } } while (j 0) { nums1[k--] nums2[j--]; } }从后往前递归地利用尾部的空余空间是原地合并类问题的经典套路。它解决的核心问题是“不额外开新数组、不覆盖未处理的元素”。只要看到题目说“原地操作”“空间复杂度O(1)”第一反应就应该是倒着处理。3.4 链表版本合并两个有序单链表热词里有人搜“合并两个有序的单链表”这是同一个问题的链表版。核心思路一样但操作细节变了因为链表不能随机访问只能用指针一个一个接。struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }注意这里用了一个很小的技巧dummy哨兵节点。如果用普通节点每次追加都得判断头节点是否为空代码会啰嗦很多。用哨兵节点可以让头节点的处理和其他节点统一这是个非常实用的小技巧写链表题时能省很多心。4. 变体与进阶去重、原地排序与多路归并4.1 合并后去重两种情况分清楚很多人问“合并排序要不要去重”答案取决于题目描述。如果明确说“结果中不含重复元素”那就需要在合并时顺手去重。实现方案不复杂比较时如果a[i]和result[k-1]相等就跳过a[i]只推进指针不写入结果。如果两边元素相等取其中一个、另一个跳过。也可以先合并再去重但不推荐——先合并再扫描去重的时间复杂度虽然同样是O(nm)但多了一轮全量遍历空间占用也更大。最容易理解的去重写进合并循环里def merge_unique(a, b): i j 0 result [] while i len(a) and j len(b): if a[i] b[j]: result.append(a[i]) i 1 elif a[i] b[j]: result.append(b[j]) j 1 else: # 相等只取一个 result.append(a[i]) i 1 j 1 result.extend(a[i:]) result.extend(b[j:]) return result这个版本“顺手去重”的关键在于两个数组各自有序重复只会发生在相同位置附近不会跨越很远所以双指针依然能准确识别。4.2 原地合并不开新数组的“倒插法”前面讲Java的LeetCode 88时已经展示了一版从后往前的原地合并。原理再拆一下两个数组总共mn个元素要放进nums1里nums1末尾恰好有n个空位。如果从头开始正着放前面刚放完的结果可能还没被处理完就覆盖掉后面还没读到的原始值但如果从尾部开始放因为每个位置最终都会被填上且填入时只取两个数组里当前较大的那个所以不会覆盖任何还没处理的元素。原地归并的深刻意义在于它把空间复杂度从O(nm)降到了O(1)。这在嵌入式开发、内存受限场景里不是锦上添花而是硬性要求。4.3 多路归并从两个数组到K个数组当你手里不是两个有序数组而是10个、100个有序数组时双指针直接退化成“每次找K个指针中最小的那个”然后把这个最小值放入结果。如果K很大每次找最小值都扫描一遍就是O(K)的代价整体复杂度过高。更科学的做法是把每个数组的当前元素放进一个小顶堆优先队列每次从堆顶取最小值然后把这个数组的下一个元素推进堆里。这样每次取最小值的复杂度从O(K)降到了O(logK)整体复杂度接近O(n log K)。Python的heapq.merge支持传入多个可迭代对象正是多路归并的标准实现。Java的PriorityQueue就是干这个的。实际业务中比如多分片数据库的合并查询、搜索引擎的倒排索引合并都是这个思路的工程化应用。4.4 特殊技巧C语言的指针数组与字符串数组热词里出现了“指针数组存放字符串”“C语言数组指针移动指定位输出字符”虽然这看起来像是在问底层细节但也确实是合并排序过程中C/C程序员最容易栽的地方。在C语言里如果你要合并的不是int数组而是一组字符串指针那么你比较的应该是字符串内容而不是指针本身。直接比较指针变量会按地址大小排结果毫无意义。正确用法是strcmp#include string.h if (strcmp(a[i], b[j]) 0) { result[k] a[i]; } else { result[k] b[j]; }同理按中文拼音排序需要locale支持按自定义规则比如忽略大小写排序需要写自己的比较函数。这些看起来是小问题但实际工程里非常容易踩坑。把“指针数组”和“排序”放在一个搜索词里八成就是遇到了这种问题。5. 常见问题与排查技巧实录5.1 为什么我的合并结果不是有序的排查方向很明确先确认输入的两个数组本身是否有序。有人拿[3, 1, 2]和[5, 4]直接跑双指针结果必然是乱的。双指针归并的前提是“输入各自有序”除非题目允许你先排序。另一种情况自定义排序规则用反了。在JavaScript里sort((a, b) b - a)是降序但你合并时用的还是升序判断两边规则不一致就会乱。所有比较操作必须使用同一个排序规则。5.2 边界条件之数组为空、长度不等这是最经典的低级错误。双指针循环结束条件是i aLen j bLen循环结束后还得手动处理剩余元素。漏掉那两段收尾代码你得到的结果就永远缺一部分。另一个边界问题是一开始某个数组就是空数组。这种情况必须在入口加判断if not a: return b if not b: return a虽然不加也能跑主循环直接跳过收尾循环把另一个数组全拷进去但显式判断会让代码意图更清晰。5.3 指针越界与数组下标错乱C语言里最容易犯的错是while (i aLen)写成了导致越界读了一个不存在的元素。记住你的指针只允许走到aLen - 1因此条件是i aLen。这类越界在大型数组上可能不会立刻崩溃但会引入随机值排错时非常抓狂。另一个常见错误是result[k]和result[k]的混用。前者是“先赋值再把下标加1”后者是“先把下标加1再赋值”。归并代码里普遍应该用前者k会把结果数组的第一个位置空出来。5.4 从数组到其他领域的“合并”迁移热词里出现了“git分支合并”“svn merge代码合并”“maven本地仓库合并”“7z.001文件合并”“B站视频音频合并”“CAD图纸合并”这些看似八竿子打不着的词本质上都共享一个心智模型把分散的多个有序单元按照某种既定规则统一整理成一个整体。比如git merge不要求两个分支的提交历史都是线性的但合并结果一定是顺序化的快照maven本地仓库合并只是把两个文件夹的内容搬到一起并处理冲突7z.001分卷压缩文件合并则纯粹是把二进制分块按顺序拼回完整文件。理解“归并”的思维框架后你会发现迁移到这些领域非常自然。不过核心算法层面真正值得你反复手写的还是“两个有序数组”这件事。它是一切多路合并的基础也是最值得花时间打磨熟练度的基本功。6. 实战经验与更进一步的学习方向6.1 双指针不只是用于合并排序在数组、链表、字符串类问题里“双指针”是一大类算法的统称。合并排序用的叫“双指针归并”还有“快慢指针”判断链表是否有环、“左右对撞指针”有序数组的Two Sum、“滑动窗口”子数组问题。三个字概括就是双向夹逼、一快一慢、同向移动。理解“谁小移谁”“谁满足条件移谁”这些规则后双指针家族的问题会越刷越顺手。6.2 归并排序的完整实现自上而下的递归与自底向上的迭代既然已经掌握了合并两个有序数组再往前一步就是亲手实现完整归并排序。递归版本核心就两步先把数组对半拆到不可再拆然后逐层归并。代码结构可以记成“分解-递归-合并”三个动作。非递归版本自底向上更偏向工程实现它先把数组拆成长度为1的块相邻两块两两归并得到长度2的块再两两归并直到只剩一块。这种写法避免了递归栈空间在某些场景比如处理链表排序格外好用。完整实现如下void mergeSort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr left, mid - left 1, arr mid 1, right - mid, temp left); }注意这里mid的计算用left (right - left) / 2而不是(left right) / 2在大量数据时能避免整数溢出这是老手才有的习惯。6.3 扩展SQL里的“合并排序”与MERGE热词里还有“mysql排序”“跨表合并”数据库里的排序归并本质上也是在跑归并算法。ORDER BY底层如果用到归并排序会和数据库缓冲区打交道多表UNION可以视作把多个结果集合并成一个结果集再进行排序去重。理解最底层的归并逻辑之后再回看数据库优化器的执行计划很多行为都在意料之中。另外Excel的“跨表合并”和数据清洗里的“合并单元格填充”虽然操作概念不同但它们都在处理一个核心问题多个来源的乱序数据如何在统一规则下重新组织。底层都是同一套“稳定归并 去重 有序聚合”的思维。6.4 性能调优与代码风格建议如果合并的数据量极大常规的result.push往数组尾部追加可能是性能瓶颈。在JavaScript里预分配数组长度或者用this“原地写”都可以避免动态扩容的开销。在C里用memcpy批量拷贝整段剩余数据当然前提是内存连续。代码风格方面给出来的例子都刻意保持了清晰命名i、j分别代表两个源数组的游标k代表结果数组的游标。面试时写出这种代码面试官一眼就能看出你对归并的理解程度。比“把所有变量都命名成temp”的代码成熟太多了。6.5 从竞赛题到业务题的思考方式竞赛场上输入规模、时间限制都很明确你可以放心用最苛刻的算法业务代码里数据规模可以被预测代码的可读性、稳定性往往比极致性能重要。比如接口只需要合并几千条数据那a.concat(b).sort()完全够用硬上双指针反而让维护成本变高。学会判断“什么时候该用严肃算法什么时候能用表达式糊弄过去”才是一个工程师从写代码到做工程的本质区别。7. 结语与避坑心得最后分享几条这些年踩坑攒下的心得。第一始终先确认输入前提。题目没提有序默认当它无序处理提了有序优先双指针。拿到题目先别动手写代码把输入条件、输出要求、空间限制这三件事确认完再想解法。第二边界条件永远是第一优先级。空数组、一个数组为空、两个数组等长、一个数组非常长、全是重复元素、全是负数和零这些测试用例要在提交之前就自己跑一遍。我在工作里见过太多质量事故追根溯源就是边界case没处理干净。第三手写伪代码比背代码更可靠。一旦理解了“谁小谁进、谁空谁停、剩者全收”这三句话任何变体你都能现场推出来。我教团队新人时从来不让他们背代码而是让他们在白板上画数组、画指针、画步骤画完自然就会了。这个内容后续你可以沿着两条线扩展往深度走去刷归并排序、逆序对、海量数据外部排序往广度走去理解多路归并、数据库执行计划、分布式系统中的数据shuffle。所有复杂系统里的“有序合并”底下都是你最早学到的这段双指针代码。两个数组合并排序入门简单但值得你反复琢磨。不要因为它太基础就跳过很多高级算法的根就长在这六字最普通的描述里。