★ FEATURED ARTICLE 1. 从一道面试题说起如果你是Java开发大概率在简历上写过熟悉常见排序算法。可真到面试官问一句归并排序为什么稳定快排为什么不稳定的时候很多人就卡住了。更别提手写一个不出Bug的归并排序——我见过不少工作三五年的开发写出来的merge方法还是会在边界条件上翻车。归并排序Merge Sort是一种基于分治策略的稳定排序算法核心操作是把两个已经有序的序列合并成一个有序序列时间复杂度稳定在O(n log n)无论数据本来是有序还是逆序它都一视同仁。它解决的不仅仅是把数组排好序这个基本问题还牵扯到外部排序、链表排序、多字段稳定排序等一系列工程场景。适合正在学习数据结构的同学、准备算法面试的求职者以及想搞明白JDK里Collections.sort为什么选归并变体的人。这篇文章我不打算泛泛讲理论而是把归并排序从思路到Java实现、从复杂度分析到工程优化、从踩坑记录到实际应用完整过一遍代码全部可以直接跑看完你不仅能写对还能说出每一步背后的为什么。2. 核心思路分治法和那个关键的合并操作2.1 分治三步走归并排序的思路一句话就能说清把数组从中间切开分别排序左半边和右半边最后把两个有序半区合并成一个有序数组。这个切开—排序—合并的过程就是典型的分治法Divide and Conquer。分治法的关键在于子问题与原问题性质相同但规模更小所以可以递归地处理下去直到子问题小到可以直接解决比如只剩一个元素天然有序。用伪代码表达就是如果数组长度 1直接返回递归出口 否则 1. 找到中点 mid把数组分成左半 [lo, mid] 和右半 [mid1, hi] 2. 递归排序左半 3. 递归排序右半 4. 合并两个有序半区你可能觉得这太简单了没错归并排序的分和治都不难难的是最后那个合——merge操作。2.2 merge操作的执行细节假设我们现在手里有两个有序数组比如左半是 [1, 3, 5]右半是 [2, 4, 6]要合成一个有序数组你会怎么做最容易想到的方法准备一个临时数组用两个指针分别指向左右两半的头部谁小就把谁放进临时数组然后指针后移直到某一边先取完再把另一边剩下的元素直接拼接过去。这个过程就是merge的核心逻辑专业说法叫双指针归并。它就像一个合并两条有序队伍的裁判每次从两队队头各拉一个人出来比个头矮的先进场直到其中一队空了剩下那队按顺序全部进场。注意一个关键细节当两个元素相等时我们应该取左半边的元素。这正是归并排序稳定的根本原因——相等的元素在合并后依然保持原来的先后顺序。这个细节如果写成if (aux[j] aux[i]判断相等时走的是 i 分支那稳定性就保住了要是写成相等时取右半稳定性就会被破坏。2.3 为什么归并排序性能稳定归并排序的时间复杂度从数学上可以这样推导设 T(n) 是排序 n 个元素的时间归并排序把问题拆成两个 n/2 规模的子问题合并操作需要线性时间 O(n)所以有递推式T(n) 2T(n/2) O(n)展开T(n) 2(2T(n/4) O(n/2)) O(n) 4T(n/4) 2O(n)一直展开到 T(1) O(1)一共 log2(n) 层每层合并的总代价都是 O(n)所以总复杂度是 O(n log n)。重要的是这个复杂度不管输入数据是顺序、逆序还是完全随机都一样。快排最坏会退化到 O(n²)而归并排序没有这个毛病。代价是它需要 O(n) 的额外空间来存放临时数组——这是归并排序最常被吐槽的点后面我会讲怎么把这个空间开销控制得更合理。3. Java实现基础版代码与逐段解析3.1 一份可以直接跑的完整代码先给你一份最经典的自顶向下递归实现我建议你自己手动敲一遍再往下看印象会深很多。public class MergeSort { private static int[] aux; public static void sort(int[] arr) { aux new int[arr.length]; sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int lo, int hi) { if (lo hi) { return; } int mid lo (hi - lo) / 2; sort(arr, lo, mid); // 排序左半 sort(arr, mid 1, hi); // 排序右半 merge(arr, lo, mid, hi); // 合并 } private static void merge(int[] arr, int lo, int mid, int hi) { // 先把 [lo, hi] 区间复制到辅助数组 System.arraycopy(arr, lo, aux, lo, hi - lo 1); int i lo; // 左半起始位置 int j mid 1; // 右半起始位置 for (int k lo; k hi; k) { if (i mid) { arr[k] aux[j]; // 左半取完了直接取右边 } else if (j hi) { arr[k] aux[i]; // 右半取完了直接取左边 } else if (aux[j] aux[i]) { arr[k] aux[j]; // 右边更小取右边 } else { arr[k] aux[i]; // 左边 右边取左边稳定性的关键 } } } }3.2 几个容易被忽略的代码细节先看mid lo (hi - lo) / 2这一行。有些教材直接写mid (lo hi) / 2两种写法在小数组上都没问题但前者避免了 lo hi 溢出虽然Java数组长度到不了那么大但好习惯从写排序算法开始养成不会亏。再看 merge 方法里的 for 循环四个分支的顺序不是随便排的。前两个分支是先处理某一边已经取完的边界情况后两个分支才是正常的比较逻辑。这个顺序必须固定否则循环里会出现数组越界。我在教学时见过很多同学把边界判断写在比较判断之后结果 i 或 j 越界排查半天才发现是顺序问题。System.arraycopy是Java提供的原生数组复制方法它是native方法比手写 for 循环快不少。这里把 arr 的 [lo, hi] 区间整体复制到 aux 的对应区间注意是复制到相同下标位置这样后面比较时aux[i]和aux[j]的语义就清晰了下标从 lo 到 mid 是左半从 mid1 到 hi 是右半。3.3 用一次实际运行来验证假设输入是 [5, 2, 4, 6, 1, 3]手动跟踪一下关键步骤。第一次调用 sort(arr, 0, 5)mid 2先处理左半 [0, 2]也就是 [5, 2, 4]。左半继续分成 [5] 和 [2, 4][5] 长度为1直接返回[2, 4]再分成 [2] 和 [4]分别返回后合并得到 [2, 4]接着合并 [5] 和 [2, 4]两个指针比较2 5 先放2再比4 5 放4最后放5得到 [2, 4, 5]。右半 [1, 3] 处理完得到 [1, 3]。最后大合并 [2, 4, 5] 和 [1, 3] 两个有序数组依次取 1、2、3、4、5最终得到 [1, 2, 3, 4, 5]。从跟踪过程能直观看到归并排序的特点它不像快排那样一边分区一边确定元素最终位置而是自底向上地不断合并有序片段。代码是递归写法但实际执行过程是先拆到底再一层层合并回去。4. 工程优化让归并排序更快更省4.1 小数组切换到插入排序纯递归的归并排序有个性能瓶颈递归到底层时会有大量长度为 1 或 2 的小数组每个小数组都要走一次完整的递归调用和 merge 流程。函数调用是有开销的而且对于规模很小的数组插入排序不仅代码简单实测效率往往更高。工程上的常规做法是加一个阈值当子数组长度小于等于某个值通常取 7 或 15时改用插入排序。public class MergeSortOptimized { private static final int CUTOFF 7; private static int[] aux; public static void sort(int[] arr) { aux new int[arr.length]; sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int lo, int hi) { if (hi - lo 1 CUTOFF) { insertionSort(arr, lo, hi); return; } int mid lo (hi - lo) / 2; sort(arr, lo, mid); sort(arr, mid 1, hi); merge(arr, lo, mid, hi); } private static void insertionSort(int[] arr, int lo, int hi) { for (int i lo 1; i hi; i) { int key arr[i]; int j i - 1; while (j lo arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } // merge 方法与基础版相同 }很多人想当然地以为把 CUTOFF 调大性能就越好我做过测试超过 15 之后收益就不明显了反而可能因为过度使用插入排序丢失归并排序原有的优势。一般取 7 到 15 之间都合理。4.2 提前检测是否已经有序归并排序对近乎有序的数组也照样走完整流程这是可以优化的。在排序过程中如果发现 arr[mid] arr[mid1]说明左半的最大值不大于右半的最小值整个区间已经是有序的不需要执行 merge。sort(arr, lo, mid); sort(arr, mid 1, hi); if (arr[mid] arr[mid 1]) { return; // 已经有序跳过合并 } merge(arr, lo, mid, hi);这一行改动在极端情况下比如数组已经排好序能把时间复杂度从 O(n log n) 降到近似 O(n)因为每一层递归都只是比较一次就返回了。Java 标准库里的 TimSort 核心思想之一就是充分利用数据的已有有序性这个优化思路跟它是同源的。4.3 关于辅助数组的思考基础版代码里aux 在 sort 入口一次性初始化避免了在递归中反复 new 数组。这一点很重要如果每次 merge 都 new 一个临时数组总分配次数会达到 O(n log n) 次GC 压力非常大性能会肉眼可见地下降。还有一个更极致的玩法在递归时交替使用 arr 和 aux 的角色减少一次复制。标准实现是每次 merge 前把数据复制到 aux合并完写回 arr这样每个元素平均会经历一次复制和一次写回。交替法可以让一部分元素在合并时直接从 aux 写回 arr、从 arr 写回 aux省掉一些来回搬运。不过这个实现的代码可读性会下降很多除非对性能有苛刻要求否则不建议在日常项目里用面试时提一嘴可以加分但写复杂了容易出Bug。4.4 自底向上的迭代版本递归版本虽然逻辑清晰但有些人就是不喜欢递归。而且自底向上的归并排序有一个额外优势代码里没有通过mid切分的问题直接从小片段开始逐层合并。public class MergeSortBottomUp { private static int[] aux; public static void sort(int[] arr) { int n arr.length; aux new int[n]; // sz 是子数组长度1, 2, 4, 8, 16 ... for (int sz 1; sz n; sz sz sz) { for (int lo 0; lo n - sz; lo sz sz) { int mid lo sz - 1; int hi Math.min(lo sz sz - 1, n - 1); merge(arr, lo, mid, hi); } } } private static void merge(int[] arr, int lo, int mid, int hi) { System.arraycopy(arr, lo, aux, lo, hi - lo 1); int i lo; int j mid 1; for (int k lo; k hi; k) { if (i mid) arr[k] aux[j]; else if (j hi) arr[k] aux[i]; else if (aux[j] aux[i]) arr[k] aux[j]; else arr[k] aux[i]; } } }这个版本最核心的坑在两层循环的边界条件。外层 sz 表示当前合并的块大小从 1 开始每轮翻倍。内层循环里lo 是左块起点mid lo sz - 1 是左块终点hi 取 min(lo 2*sz - 1, n-1) 是为了处理数组长度不是 2 的整数次幂的情况——最后一块可能凑不满。如果这块边界写错要么数组后半段没排序要么直接抛 ArrayIndexOutOfBoundsException。我写这段代码的时候踩过一次很隐蔽的坑内层循环条件写成了lo n导致数组长度为 2 的幂时一切正常长度不是 2 的幂时最后一轮多了一次无效合并——表面看结果对但循环多跑了。建议初学的时候在纸上画 n 10、sz 从 1 到 8 的完整过程把每个 lo、mid、hi 都列出来能少走很多弯路。5. 实战中容易踩的坑5.1 边界条件写错导致数组越界最常见的Bug出现在 merge 方法的 for 循环里。你可能觉得先判断 i mid 和 j hi是自然而然的但实际写代码时很多人会先比较 aux[i] 和 aux[j]这会导致当 j 已经等于 hi1 时还要访问 aux[j]直接越界。我建议把 merge 方法固定成模板两个边界判断永远在最前面然后是严格的 取小者 判断最后是相等时取左边。这个模板我用了很多年从来没出过边界问题。5.2 稳定性被悄悄破坏什么叫稳定排序就是排序前后相等元素的相对顺序不变。如果我们要排的是一个对象数组而对象有两个字段先按主字段排序再按副字段排序稳定的排序算法能保证第二次排序不会破坏第一次排序的相对顺序。这就是多字段排序的标准做法。归并排序的稳定性来自 merge 中的相等处理aux[j] aux[i]时取右边否则取左边。有些优化过的写法为了减少比较次数把条件改成aux[j] aux[i]这时相等元素会优先取右半稳定性就没了。如果你的代码后来又嵌套了其他排序这种不稳定会传导出去排出来的结果在某种业务语义下是错的——这种Bug极其隐蔽因为结果看起来没有乱只有在特定输入下才会暴露。5.3 空间复杂度误判很多人在面试时说归并排序的空间复杂度是 O(1)这是错的。递归版本的归并排序需要 O(log n) 的递归栈空间和 O(n) 的辅助数组空间合起来是 O(n log n)大O记法下就是 O(n)。如果面试官追问为什么不是O(1)要能答出两个点辅助数组是必须的原地归并的实现非常复杂且常数因子很大递归栈虽然每层很小但层数是 log n 量级。我见过不少候选人在这道送分题上失分挺可惜的。5.4 递归深度与栈溢出归并排序的递归深度是 log2(n)100万数据量大约 20 层理论上不会栈溢出。但如果你写的递归出口不是长度1就返回而是长度0或者干脆漏了出口那就真会爆栈。排查这类问题最快的办法在 sort 方法开头打印 lo 和 hi看递归是不是在一个区间内反复进出——通常这种Bug不是死循环而是mid计算导致区间没有缩小。另外一个实际工程里的坑如果归并排序的对象是链表而不是数组递归版本依然可以用但因为归并排序需要随机访问中间位置链表上找 mid 要 O(n) 时间每一层多个 O(n)总复杂度会变成 O(n log²n)。链表的归并排序有专门的写法不能简单套用数组版本。6. 归并排序的影子在哪儿6.1 JDK里的归并变体打开JDK源码Collections.sort 对对象排序用的不是快速排序而是一套叫 TimSort 的算法。TimSort 本质上是归并排序的进化版它先把数组按天然有序段run切分再用归并的方式把各个段合并同时大量利用插入排序处理短片段。为什么对象排序用它而不是快排因为对象排序要求稳定而快排做不到稳定。这个细节说明归并排序绝不是只活在课本里的算法你每天调用的 sort 方法底层很可能就是它的后代。6.2 外部排序的基石当数据量大到内存装不下时归并排序几乎是唯一的选择。外部排序的标准流程把大文件切成可以装进内存的块每块排序后写到磁盘然后用K路归并逐个合并这些有序块。这个多路归并的思想直接脱胎于归并排序的merge操作只是从两路变成多路用堆来优化找最小值的效率。我当初做日志分析的时候处理过几十G的文本文件就是靠这个思路分块排序、多路归并、边读边写内存占用始终控制在几十兆以内。6.3 什么时候该用、什么时候不该用归并排序适合的场景数据量很大但你能接受 O(n) 额外空间要求稳定排序数据存储在链表上需要外部排序以及对最坏情况性能有严格要求的系统。不适合的场景数据量小直接插入排序更快对空间极度敏感嵌入式环境排序的是基本类型数组而且不需要稳定快排加随机化更划算。Java的 Arrays.sort 里其实做了双重选择基本类型数组用快速排序不要求稳定对象数组用归并排序变体要求稳定。这个设计本身就是对什么时候该用什么排序算法的最好示范。最后说点实际操作中的感受每次写归并排序的代码我都会先在纸上把 merge 的四个分支顺序画一遍确定左半取完右半取完右边小左边小于等于右边这四种情况都能正确处理。写熟了之后这四种情况其实就是四行判断顺序固定了闭着眼睛都能写对。调试的时候有个小技巧在测试类里用随机数组验证——生成随机数据排序后再和 Arrays.sort 的结果逐元素比对再试一下全逆序、全相同、只有两个元素这些边界情况。我之前带的实习生在 merge 里把hi - lo 1写成hi - lo导致每次漏复制最后一个元素就是在随机大数据测试下抓出来的。归并排序的魅力不在于排序本身而在于它把一个看似复杂的问题拆成了足够小、足够清晰的子问题然后用一种朴素却严谨的方式把答案拼装回去。这种分治思想比算法本身更值得带走。
阅读完成 · 觉得有帮助？
