企业官网建设流程全解析

搞过一次大数据量排序之后，我才真正意识到递归版归并排序在教学上和工程上完全是两码事。理论课上讲归并排序，教科书永远是递归写法，简洁漂亮；但真到了处理大批量数据的时候，频繁的临时数组分配和函数调用开销会让人想把代码整个推翻。后来我把递归版改成非递归版，整个排序过程的内存分配降到一次，逻辑也变得更可控，这才算把“归并排序——递归与非递归的双重实现”这块骨头啃透了。

这篇文章我会把两种实现从核心原理到完整代码、再到边界推导全部拆开讲，最后补上工程中的优化经验和选型建议。无论你是刚学数据结构、正在准备面试，还是需要在项目里自研一个排序组件，都应该能从里面找到直接能抄走的东西。

1. 归并排序到底在归并什么：有序区间合并这件事

归并排序的英文名是 Merge Sort，它的要害就在 Merge 这个词上。和快速排序那种“边划分边排序”的思路不一样，归并排序先把数组切碎，再靠一次次有序合并把整个数组拼回有序。理解了这个操作，后面递归和非递归两种写法都只是“怎么安排合并次序”的问题。

1.1 两路归并：把两个有序序列合成一个有序序列

假设我有两个已经排好序的数组，左边是 [1, 3, 5]，右边是 [2, 4, 6]，要把它们合并成一个大的有序数组。做法很直观：同时看两边的头部元素，谁小就先取谁。第一次比 1 和 2，取 1；第二次比 3 和 2，取 2；第三次比 3 和 4，取 3，以此类推，最后剩下的 6 直接收尾。合并结果是 [1, 2, 3, 4, 5, 6]。

这个过程的时间复杂度是线性的 O(n)，因为每个元素最多被比较和搬运一次。你可以把它想象成两堆已经按大小叠好的扑克牌：每次只看两堆最上面那一张，抽出更小的一张放到结果堆。整个过程只需要反复“看牌堆顶、抽牌”，不需要跳来跳去。

归并排序的整体策略也就清楚了：一个无序数组，先切成两半，把左半边排好，再把右半边排好，最后用这个合并操作把两个有序半边拼起来。切到什么时候为止？切到子数组只剩一个元素的时候，单个元素天然有序，直接返回。这就是所谓的分治思想——把大问题拆成两个结构相同的小问题，小问题解决后，再把答案合起来。

1.2 merge 函数的实现细节

merge 就是把上面这套“两路归并”落成代码。给定一个数组 arr、左边界 left、中间位置 mid、右边界 right，并且保证 arr[left..mid] 和 arr[mid+1..right] 都已经升序，merge 负责把整个区间变成升序。基础版本如下：

private static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, 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++]; } for (int p = 0; p < temp.length; p++) { arr[left + p] = temp[p]; } }

我见过不少初学者在这里写arr[i] < arr[j]，少了一个等号，这是会破坏稳定性的。归并排序是稳定排序，所谓稳定是指：如果两个元素相等，它们排序后的相对位置和排序前保持一致。所以遇到相等元素时，必须先取左半部分那个，也就是要写成<=而不是<。

temp 数组是每次 merge 临时开辟的，这一步后面要重点优化。最后那个循环负责把临时数组里的数据写回 arr 的对应区间，如果漏掉它，合并结果只会留在 temp 里，下一轮排序根本用不上。

1.3 稳定性的来源和意义

像快速排序、堆排序这类算法，遇到相等元素时顺序可能被打乱，叫不稳定排序。归并排序天然稳定，靠的就是上面那句<=。

稳定到底有什么用？举一个最简单的例子：一批订单先按时间排序，然后希望按用户 ID 分组，同时要求同一个用户下的订单仍然保持时间顺序。如果你用不稳定的快排按用户 ID 排，时间顺序会被打乱；用稳定排序按用户 ID 排，相同用户 ID 的记录会保持原来的时间顺序。很多多字段排序场景都有这个需求，后面第 6 节还会展开讲。

2. 递归实现：自上而下的分治，代码最直观

递归版归并排序是数据结构教材里的常客，因为它把分治思想表达得最直接。先把大数组切成两半，排序，再合并，代码结构几乎就是把思路翻译了一遍。

2.1 递归的三个基本要素

写任何递归，都要先回答三个问题：终止条件是什么？子问题怎么划分？子问题的结果怎么合并？归并排序的答案是：

• 终止条件：left >= right，区间为空或只有一个元素，天然有序，直接返回。
• 子问题划分：取中点 mid，排序左半区间[left, mid]，再排序右半区间[mid+1, right]。
• 结果合并：调用 merge，把两个有序子区间合并成一个。

代码很短：

public static void mergeSortRecursive(int[] arr, int left, int right) { if (left >= right) { return; } int mid = left + ((right - left) >>> 1); mergeSortRecursive(arr, left, mid); mergeSortRecursive(arr, mid + 1, right); merge(arr, left, mid, right); }

注意 mid 的写法。很多同学习惯直接写(left + right) / 2，这在 left 和 right 都是接近上限的整数时，left + right可能溢出，变成负数索引，程序直接崩。用left + ((right - left) >>> 1)或者left + (right - left) / 2都能避开这个问题。工程代码里养成这个习惯不亏。

2.2 递归调用过程怎么展开

用数组[38, 27, 43, 3, 9, 82, 10]举例。初始 left=0, right=6, mid=3。程序会先递归排序左半边[0..3]，这个过程又拆成[0..1]和[2..3]。[0..1]再拆成[0]和[1]，两个单元素区间直接返回，然后合并出[27, 38]。[2..3]类似，合并出[3, 43]。再合并[0..3]，得到[3, 27, 38, 43]。右边[4..6]也这样处理，最后把两个大有序区间合并，整个数组有序。

从调用轨迹看，递归版是深度优先的。它会先把左半边彻底排好，再去碰右半边。每次 merge 发生时，参与合并的两个子区间都已经全局有序，所以 merge 里只需要线性比较就好。

2.3 递归版真正让人不舒服的地方

递归版逻辑清楚，但工程上不是没有代价。第一，每次递归调用都有栈帧压栈、弹栈，以 100 万元素为例，mergeSort 函数大概会被调用 200 万次。第二，如果直接用最基础版的 merge，每个 merge 都会 new 一个临时数组，小数组反复分配，大数组一次分配大块内存，GC 压力非常明显。我前面提到那个数据处理任务，跑完一次排序，内存曲线像锯齿一样，就是这里造成的。

当然，递归深度本身只有 O(log n)，以 10 亿数据量来算也就 30 层左右，所以“递归导致栈溢出”在归并排序里通常是伪命题。真正需要关注的是函数调用开销和临时数组分配，这一点决定了后面非递归版本值得认真学习。

3. 非递归实现：自底向上的宽度翻倍，边界是重头戏

非递归版归并排序也叫自底向上归并。它不递归切分，而是直接把每个元素看成有序区间，然后从长度为 1 的区间开始，相邻两个区间一轮一轮地合并，区间宽度每次翻倍。

3.1 从“切分”改成“拼接”

递归版是先决定一个大区间，然后一层层往下切；非递归版反过来，先处理最小区间，再逐步扩大合并粒度。

外层循环一个变量 width，表示当前这轮合并时每个有序区间的基础长度。第一轮 width = 1，相邻的两个单元素合并成有序对；第二轮 width = 2，相邻的两个有序对合并成 4 个元素的有序块；第三轮 width = 4，以此类推。当 width 超过数组长度 n 时，整个数组已经在一个大有序区间里，排序完成。

3.2 迭代版核心代码

public static void mergeSortIterative(int[] arr) { int n = arr.length; for (int width = 1; width < n; width <<= 1) { for (int start = 0; start < n - width; start += width << 1) { int mid = start + width - 1; int end = Math.min(start + (width << 1) - 1, n - 1); merge(arr, start, mid, end); } } }

这段代码不长，但内层循环的三个边界表达式，第一次接触的人几乎都会写错。我建议你不要直接背，而是推一遍。

3.3 边界条件推演：为什么是 n - width？

先说start < n - width。start 是左半区间的起点，这个条件保证左半区间存在，并且右边至少还有一个元素可以跟它合并。如果 start 已经大于等于n - width，说明剩下的元素不足一个 width，根本不存在右半区间，强行合并就会越界。

再看mid = start + width - 1。这是左半区间的末尾。因为 start 最大是n - width - 1，所以 mid 最大是n - 2，不会越界，右边至少还有一个元素 index = n - 1。

最后看end = Math.min(start + 2 * width - 1, n - 1)。右半区间的理论末尾是start + 2 * width - 1，但数组长度不一定是 2 的幂，末尾可能不够宽，所以必须用 min 截断到 n - 1。这样最后一次合并就可以处理“左侧完整、右侧残缺”的情况。

拿 n = 5 的数组[a, b, c, d, e]走一遍：

• width=1：合并[0..1]（a、b），合并[2..3]（c、d），e 落单不处理。start=0 时 mid=0, end=1；start=2 时 mid=2, end=3；start=4 不满足 start < 4，循环结束。
• width=2：start=0 时 mid=1, end=3，合并[0..3]，即有序的[a,b]和有序的[c,d]合并，e 落单。
• width=4：start=0 时 mid=3, end=4，合并[0..3]和[4]，把 e 也拼进来，完成后整个数组有序。

注意一个细节：非递归版处理“长度不是 2 的幂”时，靠的是 end 截断，而不是往数组后面补哨兵。有些写法喜欢补一个无穷大，把长度凑成 2 的幂，这在业务数据不可控时很容易出问题，后面讲哨兵坑的时候会细说。

非递归版的中间状态也很有意思：每一轮结束后，数组里所有宽度相同的区间各自有序，但块与块之间未必有序。这和递归版那种“左半边先完全有序”的中间态完全不同。对于最终排序结果没有影响，但在某些增量排序场景下，这种规整的中间状态更好描述、更好恢复。

4. 递归与迭代的全面对比：复杂度、顺序与调用开销

两种实现底层共享同一个 merge，稳定性完全一致，差别主要集中在调用方向、辅助空间和中间状态上。

4.1 复杂度：时间都是 O(n log n)，空间差在递归栈

时间复杂度上，两者都是 O(n log n)。每一轮合并的总规模是 n，区间宽度每轮翻倍，轮数是 log n，所以总工作量是 O(n log n)。最关键的是，归并排序的最好、最坏、平均时间复杂度都是 O(n log n)，这一点比快速排序稳定得多——快排最坏会退化到 O(n²)，归并不会。

空间复杂度略有差别。递归版如果每次都 new 临时数组，空间峰值是 O(n)，但递归栈额外占 O(log n)。非递归版没有递归栈，临时数组 O(n)，合起来仍然是 O(n)。真正影响体验的不是栈深，而是临时数组的分配次数。基础版 merge 每次调用都 new 一次，百万数据量的递归版会分配超过一百万个临时数组，尽管大多数很小，但 GC 压力实实在在。

4.2 合并顺序差异带来什么

递归版是深度优先：从根节点出发，一路递归到最左边的单元素，然后一层层合并，把整个左半边排好，才转向右半边。如果你在排序过程中打印数组，会看到左边逐渐有序，右边还保持原样。

非递归版是“分层推进”：第一轮结束，所有相邻元素组成有序对；第二轮结束，所有长度为 4 的块有序；第三轮结束，所有长度为 8 的块有序。这种访问模式对 CPU 缓存很友好，因为每一轮都是从头到尾线性扫描数组，几乎没有随机跳跃。递归版的访问是跳跃式的，虽然局部性也不算差，但层级切换更多。实测大数组上非递归版通常会快一点点，但差距一般不大，并不是换一个版本就天翻地覆。

另外一个容易被忽略的差异是“可中断性”。如果排序允许被打断，比如排序超过时间预算就先保存中间状态，非递归版每轮结束后的状态是一个清晰可描述的稳定态，恢复起来很容易；递归版的中间态则是一棵没走完的递归树。虽然实际排序很少这么干，但理解这点对设计增量排序有启发。

4.3 选型建议

教学、面试、写算法题，用递归版就好，思路清晰不容易错。自研排序工具、嵌入式环境、数据量大且对调用开销敏感，优先上非递归版。如果再叠加下一节说的临时数组复用，非递归版在工程上的优势会更明显。

5. 实战优化：临时数组、哨兵与小区间切换

到这里两种写法都会了，但直接拿去生产环境还不够。下面这几个优化点是我实际排序时踩过的坑或者切实收益最大的改法。

5.1 一次分配临时数组，复用到最后

这是归并排序最重要的工程优化。基础版 merge 每次都 new 一个数组，改成在排序入口只分配一次长度为 n 的 temp，所有 merge 共用：

private static void mergeWithTemp(int[] arr, int[] temp, int left, int mid, int right) { int i = left, j = mid + 1, k = left; 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++]; } for (int p = left; p <= right; p++) { arr[p] = temp[p]; } }

入口处只分配一次：

public static void mergeSort(int[] arr) { int[] temp = new int[arr.length]; mergeSortRecursive(arr, temp, 0, arr.length - 1); }

这个 merge 版本和基础版思路一致，只是把临时数组从“每次新开”变成“全程复用”。它直接读取 arr 上两个有序子区间，写入 temp，最后整体回写 arr。有人担心合并过程中 temp 的数据会不会覆盖 arr 还没读到的元素——不会，因为 temp 是独立数组，读写互不干扰；读区永远是 arr 上两个不相交的有序段，写区永远是 temp。最后回写时，arr 对应区间被整体更新成有序版本，后续合并继续读它，逻辑闭环。

还有一种常见写法：先把arr[left..right]整体拷到 temp，再从 temp 里取两段比较写回 arr。两种都对，性能差距很小。我这里选的版本少了一次批量拷贝，但可读性略低，看个人喜好。

5.2 哨兵值的坑

不少教材为了简化 merge 里的 while 判断，会在左右两个子数组末尾放一个“无穷大哨兵”，这样不需要判断指针是否越界，比较到哨兵自然收尾。思路巧妙，但工程里我不推荐，原因有三。

第一，数据里如果本身就有Integer.MAX_VALUE，哨兵就失效了，合并逻辑可能在相等值上出错。第二，排序对象数组时，哨兵不好定义，用 null 做哨兵又容易在比较时触发空指针。第三，哨兵只是省掉几次越界判断，收益很小，却给排序组件引入了“数据范围必须小于哨兵”的隐含约束。

我的习惯是：基础组件排序，正确性优先于微优化，条件判断写全，不用哨兵。真要追求那点常数，先把临时数组复用和小区间插入排序做了，收益大得多。

5.3 小区间切换插入排序

归并在递归到很小区间时，比如元素个数少于 16，继续递归调用和分配临时数组的开销反而比简单排序高。插入排序在小区间上常数极小，没有递归调用，代码也简单。工程实现里会在递归版里加一个阈值：

private static final int THRESHOLD = 16; public static void mergeSortRecursive(int[] arr, int[] temp, int left, int right) { if (right - left <= THRESHOLD) { insertionSort(arr, left, right); return; } int mid = left + ((right - left) >>> 1); mergeSortRecursive(arr, temp, left, mid); mergeSortRecursive(arr, temp, mid + 1, right); mergeWithTemp(arr, temp, left, mid, right); }

插入排序代码：

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; } }

阈值选在 8 到 32 之间都是常见做法。别小看这一步，它能省掉大量最底层的递归调用，实测对中等规模乱序数组有明显提升。

5.4 自然归并：利用原本就有的有序片段

非递归版默认从 width = 1 开始，等于把每个单元素都当成一个有序段。但如果输入数据里本来就有一段段升序子序列，从 1 开始就浪费了更早的信息。

自然的做法是先扫描一遍数组，把连续升序片段识别成初始有序段。比如[1, 3, 5, 2, 4, 8, 0]扫描完得到初始段[1,3,5]、[2,4,8]、[0]三段，合并时从这三段开始，而不是从 8 个单元素开始。数据越接近有序，收益越大。像 Java 和 Python 标准库底层用的 TimSort，核心思想就是自然归并加二分插入排序，能让接近有序的输入跑到接近 O(n) 的时间。想深入了解归并优化的同学，研究 TimSort 是很值得的下一步。

6. 工程选型：稳定排序、语言标准库与外部排序

归并排序在算法书里看起来是个“基础排序”，但真正到了工程里，它的地位远比想象中高。

6.1 标准库里的归并排序

很多语言的排序接口都内置了归并思想。Java 里排序对象数组用的Arrays.sort(Object[])是稳定的 TimSort 变种，Collections.sort()同理；排序基本类型数组的Arrays.sort(int[])用的却是双轴快排，因为基本类型的相等没有“相对顺序”概念，不需要稳定。C++ 的std::stable_sort是稳定排序，通常由归并实现；std::sort是不稳定的内省排序。Python 内置的list.sort()和sorted()也是稳定的 TimSort。

你可能会疑惑：标准库都封装好了，为什么还要自己写？两个原因：一是面试和算法题经常要求手写；二是有些场景标准库帮不上忙，最典型的就是数据量大到内存装不下，必须自己实现外部排序流程。

6.2 什么时候必须用稳定排序

回到第 1 节那个稳定性问题。多字段排序时，稳定排序能给你省很多组合键的麻烦。比如一批记录先按姓名排，再按分数排，如果分数相同，希望保持姓名的原有顺序，稳定排序直接两轮搞定：第一轮按姓名排，第二轮按分数排。不稳定排序就得把姓名和分数包装成组合键才能保证同样的效果。

在面向对象语言里，对象字段可能很复杂，复制组合键有额外开销，稳定排序就显得尤为重要。这也是为什么 Java 对对象数组必须用稳定的归并变种，而对基本类型数组反而放心用快排。

6.3 外部排序：内存装不下时，归并几乎是唯一选择

归并排序还有一项其他比较排序不具备的能力：天然适合外部排序。假设内存只有 1GB，要排序一个 10GB 的文件，可以这样做：

1. 把文件切成 10 个 1GB 的块，逐块读入内存，用任意排序算法排好，写回磁盘。
2. 对磁盘上多个有序块做多路归并：同时打开所有块的输入流，每个流维护当前头部元素，每次取最小的一个写入输出文件，再从那块补充下一个元素。
3. 全部写完，输出文件就是一个有序大文件。

快速排序和堆排序做不到这一点，因为它们要求数据能够整体随机访问。而多路归并只需要每个块当前头部的几个元素在内存中，配合缓冲区就能稳定工作。数据库的排序算子，底层干的就是这回事。

多路归并还有个进阶话题：当路数 K 很大时，每次从 K 个头部里选最小值用线性扫描成本高，常见优化是维护一个大小为 K 的堆或败者树，把单步代价降到 O(log K)。这个东西展开可以单独写一篇，这里你只需要记住结论：归并排序能撑起从几千到几亿数据的排序场景，靠的就是稳定和可外部化这两个特性。

我自己动手实现排序的时候有个固定套路：面试和快速验证思路用递归版，因为不容易写错；真正要放进项目里跑的代码，用非递归版配一次 temp 复用，再根据数据规模决定要不要加小区间插入排序。归并排序最值得记住的从来不是某段具体代码，而是“稳定排序”和“外部排序可行”这两个能力，它们让这个几十年前的老算法在今天的大数据和数据库场景里依然是核心角色。如果你正准备手写一个排序，先想清楚：数据能不能全放进内存？需不需要保持原有相对顺序？这两个问题的答案会直接帮你决定该选归并还是快排。