排序算法是算法学习里绕不开的主题。很多人一开始学的是冒泡、选择、插入这类 O(n²) 的入门排序然后有一天突然碰到归并排序——代码骤然变长还有递归第一反应往往是“这玩意儿到底在干嘛”。但归并排序值得你认真搞懂因为它可能是你接触的第一个时间复杂度稳定在 O(n log n) 的通用排序算法也是分治Divide and Conquer思想最经典的落地案例。它和快速排序、堆排序一起被称为“三大高级排序”但归并排序有一个它们都比不了的优点无论输入数据是正序、倒序还是乱序它都能稳定地跑出 O(n log n)。就凭这一点它在工业级场景里占着不可替代的位置。下面我不打算讲得太“教科书”我会从合并两个有序数组这个核心操作讲起带你手拆一遍完整流程给出 Java 和 Python 的算法模板再聊一聊实战里的坑、优化思路和几个隐藏应用。无论你是准备面试还是想系统搞懂排序这篇应该能让你把归并排序吃透。1. 先把“合并两个有序数组”这个操作刻进脑子里1.1 分治三步走分解、解决、合并归并排序的思想一句话就能说清楚——把数组从中间一分为二先把左边排好再把右边排好最后把两个有序的半个数组合并成一个整体有序的数组。这就是分治思想里的三个步骤分解Divide、解决Conquer、合并Combine。很多人第一次接触递归时容易卡住心里会想“左边排好怎么排好难道不是又调了一遍归并排序吗”没错就是再调一遍自己。你觉得它没排好是因为递归还没走到头事实上它会一直拆拆到每个子数组只剩下一个元素为止。一个元素当然是有序的——这不需要证明。然后从最底层开始一层一层地合并回去整个数组最终就会有序。这个过程有个关键的心态转变对于递归函数你只需要相信它“能干完活”。把mergeSort(arr, left, mid)当成一个黑盒它的语义是“把 arr 里 [left, mid] 这段排好序”至于它内部怎么做到你暂时不用管。把注意力集中在 merge 这一步——前面两段都已经有序了怎么把它们合并成一段有序的大区间。只要这一步是对的整个算法的正确性就立住了。1.2 用“两堆扑克牌”理解合并操作合并是归并排序的灵魂。两个已经有序的数组或者同一个数组的两个相邻区间用一个临时数组做中转两个指针分别指向两边的开头每次比较指针上的元素谁小谁进临时数组对应指针后移。当某一边全部放完另一边剩余的元素一次性拷贝过去。用扑克牌类比一下假设你左手拿的牌从小到大排好了右手拿的也是从小到大排好的现在要合成一摞。你不会先把左手的大牌放下去再把右手的小牌塞进去——你只会一直盯着两边的牌顶每次抽出较小的那张放到结果牌堆的底部。谁先谁后不确定但结果一定是全局有序。这个过程的时间复杂度是 O(n)因为每个元素最多被比较一次、移动一次。但注意合并是借用临时数组完成的这正是归并排序空间复杂度的来源。很多初学者以为归并排序能做到 O(1) 空间其实不对它需要一个额外的 O(n) 空间来辅助合并。到这里你可能已经意识到归并排序的所有工作其实都发生在 merge 这一步递归分解本身不干任何事只是把一个复杂问题拆成简单子问题。这也是为什么很多人说掌握了 merge归并排序就学会了一半。2. 别光看代码把[38, 27, 43, 3, 9, 82, 10]完整走一遍2.1 递归拆分的执行顺序我学递归排序习惯拿一个具体数组硬走一遍。这次用经典例子arr [38, 27, 43, 3, 9, 82, 10]初始调用mergeSort(arr, 0, 6)。递归拆分过程是“先左后右、走到底再回头”也就是深度优先DFS顺序。很多初学者以为归并排序会把数组对半劈成两份同时处理其实在单线程递归里不是这样左半边会从大到小全部拆完、合并完才开始处理右半边。从最外层看mergeSort(0, 6)先算出 mid 3然后一头扎进左半边mergeSort(0, 3)左半边算出 mid 1继续扎进mergeSort(0, 1)再算出 mid 0然后调用mergeSort(0, 0)和mergeSort(1, 1)这两个都是一元素区间直接返回。接着执行merge(0, 0, 1)把[38]和[27]合并成[27, 38]。到这里最左下方的两个兄弟节点处理完毕。回到mergeSort(2, 3)mid 2mergeSort(2, 2)和mergeSort(3, 3)都直接返回执行merge(2, 2, 3)把[43]和[3]合并成[3, 43]。然后回到上一层执行merge(0, 1, 3)把[27, 38]和[3, 43]合并成[3, 27, 38, 43]左半边整体有序。接着才是右半边mergeSort(4, 6)mid 5同样先处理mergeSort(4, 5)最终把[9]和[82]合并成[9, 82]mergeSort(6, 6)直接返回然后执行merge(4, 5, 6)把[9, 82]和[10]合并成[9, 10, 82]。最后回到最外层执行merge(0, 3, 6)把[3, 27, 38, 43]和[9, 10, 82]合并成最终的[3, 9, 10, 27, 38, 43, 82]。注意这里 mid 的计算用的是mid left (right - left) / 2为什么不直接写(left right) / 2因为当 left 和 right 都是很大的正整数时left right 可能溢出 int 类型。虽然日常刷题很难遇到这么大的数组但养成这个写法没有坏处面试官问起来也能加分。2.2 合并阶段的关键现场上面案例里最值得仔细看的是最后一次merge(0, 3, 6)。此时前四个元素是[3, 27, 38, 43]后三个是[9, 10, 82]两边各自有序。合并过程如下步骤比较元素较小值临时数组谁移动了13 vs 93[3]左指针后移227 vs 99[3, 9]右指针后移327 vs 1010[3, 9, 10]右指针后移427 vs 8227[3, 9, 10, 27]左指针后移538 vs 8238[3, 9, 10, 27, 38]左指针后移643 vs 8243[3, 9, 10, 27, 38, 43]左指针后移7左半耗尽82[3, 9, 10, 27, 38, 43, 82]右指针后移注意第 7 步左半已经遍历完右半还剩一个 82不需要再比较直接拷贝过去即可。代码里对应的就是后两个 while 循环。在整个归并排序过程中这样一个流程会在不同层面反复执行直到整个数组有序。在这个合并过程中你还可以观察到一件有意思的事每个元素的“归属”其实发生过多次变化。38 在第一次 merge 里先被放到临时数组的第 2 个位置后来在第三次 merge 里又被放到第 4 个位置最后在最终 merge 里出现在第 5 个位置。元素的移动不是一步到位的而是随着归并层级的升高一步步被推到最终位置。这一点和插入排序“一次移动一个位置”完全不同也是归并排序能保证 O(n log n) 的原因之一——每次合并都是线性操作但层级只有 log n 层。3. 算法模板Java 和 Python 双版本可以直接抄作业3.1 Java 模板递归版Java 版本推荐“静态辅助方法 每次只申请需要的临时数组”这种写法public class MergeSort { public static 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, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left; int j mid 1; int k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } System.arraycopy(temp, 0, arr, left, temp.length); } public static void main(String[] args) { int[] arr {38, 27, 43, 3, 9, 82, 10}; mergeSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }几个细节值得单独说明mergeSort 的终止条件是left right。很多写法会写成left right功能上一样但在防御非法区间上更稳。合并时while (i mid j right)的判断条件是不是。漏掉等号会导致一个元素没进临时数组排序结果会丢数据。if (arr[i] arr[j])用而不是这个细节决定了稳定性。相等时优先取左半边元素才能保留原始相对顺序。如果你读过《算法导论》可能记得它在合并时会往数组末尾放一个哨兵元素比如 Integer.MAX_VALUE这样能省掉两个 while 去处理剩余元素的逻辑。这个技巧代码更统一但需要保证原数组中不存在等于哨兵的值否则比较结果会被干扰。实际工程中我更喜欢两个 while 的写法更直白、可控。3.2 Python 模板最简洁但注意内存开销Python 有一个非常直观的写法利用切片和列表def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result这个版本好懂但有个明显的毛病每次递归都会创建新的切片和新的 result空间开销比 Java 版本大不少排序大数组时内存压力很大。刷题或者写脚本时可以用但如果你想更接近底层实现推荐下面这个传索引范围的版本def merge_sort(arr, left, right): if left right: return mid (left right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid 1, right) temp [] i, j left, mid 1 while i mid and j right: if arr[i] arr[j]: temp.append(arr[i]) i 1 else: temp.append(arr[j]) j 1 if i mid: temp.extend(arr[i:mid 1]) if j right: temp.extend(arr[j:right 1]) arr[left:right 1] temp3.3 非递归版本自底向上面试官有时会追问递归版本写熟之后你可能会被追问“不用递归能写吗”能。归并排序有一个典型的自底向上实现思路和递归版反过来——先把数组拆成大小为 1 的块每两个相邻块合并成一个大小为 2 的有序块再把相邻的大小为 2 的块两两合并成大小为 4 的有序块……直到整个数组有序。public static void mergeSortBottomUp(int[] arr) { int n arr.length; for (int size 1; size n; size * 2) { for (int left 0; left n - size; left 2 * size) { int mid left size - 1; int right Math.min(left 2 * size - 1, n - 1); merge(arr, left, mid, right); } } }这个版本的 merge 函数和递归版完全通用。它把“分”省掉了通过迭代控制合并区间。注意right Math.min(left 2 * size - 1, n - 1)当数组长度不是 2 的幂时最后一组可能凑不满必须截断到数组末尾否则会越界。4. 复杂度与稳定性为什么归并排序的时间复杂度能“一直很稳”4.1 递推式推导T(n) 2T(n/2) O(n)归并排序把规模为 n 的问题拆成两个规模为 n/2 的子问题每次合并的代价是遍历一次区间 O(n)所以有T(n) 2T(n/2) O(n)套主定理Master Theorema 2b 2log₂2 1f(n) O(n) 正好是 Θ(n¹)满足主定理第二种情况所以 T(n) Θ(n log n)。如果你不习惯主定理就画递归树根节点的合并代价是 n第二层有两个节点每节点的合并代价是 n/2加起来还是 n第三层四个节点代价加起来依然是 n。每一层都是 O(n)递归树高度是 log₂ n所以总复杂度 O(n log n)。这里有个非常值得记住的结论快速排序的平均复杂度也是 O(n log n)但最坏情况会退化成 O(n²)只有归并排序无论最好、最坏、平均都稳定在 O(n log n)。面试题“有没有最坏情况也是 O(n log n) 的排序算法”——归并排序就是标准答案。4.2 空间复杂度O(n) 的临时数组是绕不开的成本归并排序需要额外数组来辅助合并。严格来说空间复杂度 O(n)辅助数组 O(log n)递归栈取大头就是 O(n)。有些人会想能不能原地归并把空间降到 O(1)理论上可以但实际代价极大。如果你试图通过元素旋转在数组内部合并合并步骤会从 O(n) 退化成 O(n²)最后整体变成 O(n² log n)得不偿失。所以归并排序的空间开销是它为时间复杂度稳定性必须付出的代价。三大高级排序放一起对比会更直观排序算法平均时间最坏时间空间稳定性归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并在时间上最稳吃空间快排通常最快cache 友好、常数小但最坏情况退化堆排省空间常数大且不稳定。提示Java 的 Arrays.sort() 对对象数组用 TimSort基于归并排序的改进版对基本类型数组用双轴快速排序。之所以对象数组必须稳定是因为对象比较代价高而且业务上往往依赖“相同属性对象保持原有顺序”。4.3 稳定性那个经常被忽略的 号稳定排序的定义值相等的元素排序后相对位置不变。归并排序的稳定性来自合并时的一个小细节——arr[i] 和 arr[j] 相等时先取左半边的元素所以代码写if (arr[i] arr[j])而不是if (arr[i] arr[j])。写成的话相等元素会先取右半边的虽然最终数组依然有序但稳定性就丢了。稳定性在什么时候重要多重排序时。比如先按姓名排一遍再按年龄排一遍稳定的排序算法能保证年龄相同的人姓名顺序是第一轮排序的结果。C STL 的 stable_sortJava 对对象排序用的 TimSort底层核心都是归并就是冲着稳定性去的。5. 实战中的坑与优化有些问题不跑一遍真的发现不了5.1 两个最常见的边界 bug我见过很多人在 merge 这儿栽跟头最常见的有两类。一类是把 while 条件里的等号写漏。i mid写成i mid导致左半边最后一个元素没进入临时数组j right写漏同理。这种 bug 非常隐蔽——当数组长度恰好是偶数、最后剩余的元素恰好来自右半边时运行结果可能照样正确换一组数据就出错。排查方法也简单所有涉及 mid 和 right 的循环边界反向检查一遍。另一类是拷贝临时数组时写错范围。Java 模板里System.arraycopy(temp, 0, arr, left, temp.length)temp.length 恰好等于 right - left 1。但如果你为了省事把临时数组申请成new int[arr.length]然后 arraycopy 时拷贝整个 temp.length就会把数组前面的残留数据也覆盖回去结果一塌糊涂。临时数组按当前区间申请拷贝范围跟着 [left, right] 走这是最不容易出错的组合。还有一个细节是循环里用到的索引。合并过程中 i 和 j 分别从 left 和 mid 1 开始很多人写着写着就把 i 初始化为 0 了结果比较的永远是原数组前几个元素。这种错误一旦发生排序结果往往“部分有序”很迷惑人。建议每次写完 merge先拿一个只有三四个元素的极端用例跑一遍比对着调试快得多。5.2 三个值得养成的性能优化习惯第一个优化小区间用插入排序。递归调用是有系统开销的当区间长度小到一定程度通常 7 到 16时直接插入排序反而更快。很多工业实现的底层都这么做。你可以这样改if (right - left 15) { insertionSort(arr, left, right); return; }对应的插入排序实现private static void insertionSort(int[] arr, int left, int right) { for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }第二个优化当arr[mid] arr[mid 1]时说明左右两个区间拼接起来已经有序这时候可以直接 return跳过 merge。这个判断在数据接近有序时特别有效可以让最好情况逼近 O(n)。第三个优化避免每次 merge 都 new 数组。可以预先申请一个和原数组一样大的 temp 数组merge 时通过参数传进来每次只操作需要的区间。内存分配减少整体性能会好不少。尤其是排序大数组时这个优化效果很明显。5.3 链表归并排序零额外数组空间的归并链表是归并排序的天然领地。数组的快排需要随机访问链表做不到除非先转成数组但归并只需要顺序遍历链表完全能胜任而且因为可以调整 next 指针它不需要额外数组——空间复杂度降到 O(log n)只剩递归栈。链表版本的三步用快慢指针找链表中点把链表切成两段。递归排序两段。合并两个有序链表只改指针不建数组。public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } ListNode mid slow.next; slow.next null; ListNode left sortList(head); ListNode right sortList(mid); return mergeTwoLists(left, right); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next (l1 ! null) ? l1 : l2; return dummy.next; }LeetCode 第 148 题“排序链表”就是这么考的。如果能在代码里顺手写出 mergeTwoLists这道题基本就过了。6. 归并排序的隐藏应用它远比“一个排序算法”值钱6.1 归并排序的变种求逆序对数量这是归并排序最经典的扩展应用。逆序对定义i j 且 arr[i] arr[j]。暴力做法是双重循环 O(n²)但用归并能在 O(n log n) 时间内数出来。思路藏在 merge 过程里当右半边的 arr[j] 小于左半边的 arr[i] 时左半边从 i 到 mid 的所有元素都大于 arr[j]——它们和 arr[j] 全部构成逆序对。所以累加 mid - i 1而不是 1。int count 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { count mid - i 1; temp[k] arr[j]; } }这里可能有人会疑惑排序过程中数组已经被局部打乱了统计还有效吗有效。因为递归统计完左右两半之后左右两半内部已经没有逆序对了剩下的逆序对只会跨左右两个区间而跨区间的逆序对恰好在这个 merge 过程中被数完。LeetCode 的“计算右侧小于当前元素的个数”“翻转对”等题本质都是这个思路的变体。把模板改成计数版本这类题目基本都能拿下。6.2 外部排序内存装不下时归并排序是工业级主力数据量大到内存装不下时几十个 G 的日志、数据库 dump多数排序算法会失效这时候需要外部排序。外部排序的核心思路就是归并排序的自底向上版本把大文件切成若干个小块每个小块都能塞进内存。每个小块读入内存排好序后写回磁盘得到一个有序段。对所有有序段做多路归并利用最小堆或败者树维护当前最小值不断输出最终生成一个完整的有序文件。数据库的排序算子、搜索引擎索引构建、大数据框架 shuffle 阶段的排序底层都有外部排序的影子。归并排序能把“超大规模数据排序”这个别人搞不定的场景变成日常操作这是它离工业界最近的地方。这里还要提一个工程细节多路归并的“路数”k 不是越大越好。k 越大每次从 k 个有序段中选最小元素的成本越高。如果朴素地线性扫描单次选最小是 O(k)整体复杂度会变大所以工业上常用最小堆或败者树把单次选最小降到 O(log k)。这就是为什么外部排序的归并阶段往往会搭配一个堆结构来用而归并排序本身只负责把两个段合成一个新段——组合方式可以很灵活。最后说说我的个人体会。我最早学归并排序的时候也觉得递归抽象、代码比冒泡长一大截心里发怵。后来真正啃下来才发现在三大高级排序里它反而是最好理解的一个——因为它的正确性几乎不需要怀疑merge 对了递归边界对了整个算法就一定对。如果你现在正卡在递归上我的建议很简单别着急背模板先拿一个数组在纸上把 2.1 那种调用过程逐步画出来。等你在纸面上把整个流程走过一遍写代码就只是把心里想的过程翻译成语法自然就出来了。这是我学归并排序收获最大的一步也是我想分享给你的核心建议。
