企业官网建设流程全解析

归并排序这个算法，几乎每个学编程的人都写过，但真正把它写到"能打"的人并不多。我见过太多版本，包括我自己早期写的，功能上没问题，跑个小数组也对，可一旦数据量上去、或者遇到特殊数据分布，性能就露馅了。这篇内容就是把我这些年反复打磨归并排序的经验整理出来，从最朴素的递归实现，一路讲到几个真正能提升性能的优化点，包括小数组切换插入排序、归并前的有序性检测、辅助数组的复用、以及迭代式自底向上实现。每个优化我都会说清楚"为什么这么做"和"实测效果大概是什么量级"，而不是甩一段代码就完事。

如果你正在准备算法面试、在写高性能排序模块、或者单纯想把基础算法吃透，这篇内容应该都能给你一些可以直接抄作业的东西。代码全部用C++写，标准控制在C++11及以上，不依赖任何第三方库，复制到本地就能编译运行。

1. 先把朴素递归版写对，再谈优化

很多人一上来就想搞优化，结果基础版本里藏着边界bug，优化反而把问题掩盖了。所以第一步，我们得有一个绝对正确的基准版本，后面所有优化都拿它做对照。

1.1 归并排序的核心思想到底是什么

归并排序本质上是分治思想最典型的应用。它把一个大数组不断对半切，切到每个子数组只剩一个元素——单个元素天然有序——然后再两两合并回去。合并的过程是：两个已经有序的子数组，用两个指针从头扫，谁小先放谁，扫完就得到一个更大的有序数组。

这里有个关键点很多人没意识到：归并排序的"排序"动作全部发生在合并阶段，拆分阶段不做任何比较。拆分只是把问题规模缩小，真正的活是merge干的。理解这一点，后面所有优化都围绕"如何让merge更高效"和"如何减少不必要的merge"展开。

用生活化的类比：就像两摞已经按身高排好的队伍，你要把它们并成一摞。你只需要看两摞各自的排头，谁矮谁先出列，重复这个动作就行，不需要重新比较整摞人。

1.2 一份可以直接编译运行的基准实现

先看基准版本，我把它写得尽量清晰，变量命名也直白：

#include <vector> #include <cstddef> void mergeRange(std::vector<int>& arr, int left, int mid, int right, std::vector<int>& buffer) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { buffer[k++] = arr[i++]; } else { buffer[k++] = arr[j++]; } } while (i <= mid) { buffer[k++] = arr[i++]; } while (j <= right) { buffer[k++] = arr[j++]; } for (int p = left; p <= right; ++p) { arr[p] = buffer[p]; } } void mergeSortRecursive(std::vector<int>& arr, int left, int right, std::vector<int>& buffer) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSortRecursive(arr, left, mid, buffer); mergeSortRecursive(arr, mid + 1, right, buffer); mergeRange(arr, left, mid, right, buffer); }

调用方式就是准备一个和原数组等大的buffer，然后mergeSortRecursive(arr, 0, arr.size() - 1, buffer)。

这里有几个细节值得单独拎出来说。第一，mid = left + (right - left) / 2而不是(left + right) / 2，是为了避免left和right都很大时相加溢出。虽然对int数组来说这个溢出在绝大多数场景不会触发，但养成习惯没坏处。第二，arr[i] <= arr[j]用的是小于等于，这个等号保证了排序的稳定性——相等元素保持原有相对顺序。如果你不需要稳定性，改成<也行，但一般没理由改。第三，merge完之后要把buffer拷回arr，这一步不能省，否则下一轮合并拿到的还是旧数据。

1.3 基准版的性能瓶颈在哪

朴素版跑起来没问题，但有几个明显的浪费。最突出的是：当某个子数组已经有序时，它仍然会被无脑合并。比如数组本身已经基本有序，递归到某一层时左半段最大值小于右半段最小值，这时候整个merge其实是白做的，直接跳过就行。这个优化后面会专门讲。

第二个浪费是递归深度。对于百万级数据，递归深度大约20层，每层都有函数调用开销。虽然现代编译器对尾递归和简单递归优化得不错，但函数调用栈的压栈弹栈成本依然存在。

第三个浪费是buffer的反复读写。每次merge都要把数据从arr搬到buffer，再从buffer搬回arr，等于每个元素在每一层都要被搬两次。对于n个元素、log n层，总搬运量是2n log n次。这个量级其实还好，但如果我们能减少搬运次数，收益是实打实的。

2. 优化一：小数组切换插入排序

这是归并排序最经典、性价比最高的优化，没有之一。原理很简单：当子数组长度小到一定程度时，插入排序比归并排序快。

2.1 为什么小数组上插入排序反而更快

插入排序的时间复杂度是O(n²)，归并是O(n log n)，按理说归并应该永远更快。但复杂度分析忽略了一个东西：常数因子。插入排序的内层循环非常简单，就是比较和移位，而且对已经接近有序的小数组，插入排序的实际比较次数远小于n²。而归并排序即使处理8个元素，也要走完整的递归拆分、merge、拷贝流程，函数调用和内存搬运的开销占比很高。

实测经验是，阈值取在7到16之间比较合适。太小了优化效果不明显，太大了插入排序的O(n²)开始拖后腿。我一般取16，这个值在多数机器上表现稳定。也有资料推荐7，具体可以自己测。

2.2 阈值到底取多少，给个实测参考

我做过一组粗略测试，对100万个随机int排序，阈值分别取0（即不切换）、7、16、32、64，重复多次取平均，大致趋势是这样的：

这个数据不是绝对的，跟机器、编译器优化等级、数据分布都有关，但趋势是稳定的：16左右是个甜点区。你可以把阈值做成常量，方便调整。

2.3 改造后的代码长什么样

改造点就一处：递归的终止条件从left >= right改成right - left + 1 <= THRESHOLD时直接插入排序。

const int INSERTION_THRESHOLD = 16; void insertionSort(std::vector<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; } } void mergeSortOptimized(std::vector<int>& arr, int left, int right, std::vector<int>& buffer) { if (right - left + 1 <= INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } int mid = left + (right - left) / 2; mergeSortOptimized(arr, left, mid, buffer); mergeSortOptimized(arr, mid + 1, right, buffer); mergeRange(arr, left, mid, right, buffer); }

注意插入排序的边界是left到right，不是从0开始，因为它是作用在子数组上的。这个细节写错的话，排序结果会乱，而且很难查。

提示：阈值不要写死在递归函数里当魔法数字，抽成常量，方便统一调整和测试。

3. 优化二：合并前先判断是否已经有序

这个优化听起来很"废话"，但实际收益在特定数据分布下非常可观，尤其是对近乎有序的数据。

3.1 一个被忽视的事实：有序时merge是纯浪费

归并排序的递归结构决定了，每次合并前，左半段和右半段各自已经有序。如果左半段的最大值arr[mid]小于等于右半段的最小值arr[mid+1]，那么整个区间[left, right]其实已经有序了，根本不需要合并。

这个判断的成本是一次比较，而省下的是一次完整的merge——涉及多次比较、多次内存读写、一次拷贝回原数组。一次比较换一次merge，这笔账怎么算都划算。

对于完全随机的数据，这个条件命中的概率不高，所以收益有限。但对于近乎有序的数据（比如只做了少量修改的已排序数组），命中率极高，性能提升可能是数倍。

3.2 加上判断后的代码与收益分析

改动很小，在调用mergeRange之前加一个if：

void mergeSortOptimized(std::vector<int>& arr, int left, int right, std::vector<int>& buffer) { if (right - left + 1 <= INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } int mid = left + (right - left) / 2; mergeSortOptimized(arr, left, mid, buffer); mergeSortOptimized(arr, mid + 1, right, buffer); if (arr[mid] <= arr[mid + 1]) { return; } mergeRange(arr, left, mid, right, buffer); }

就多了三行。对于随机数据，这三行带来的额外比较开销可以忽略；对于有序或近乎有序数据，它直接把大量merge变成了一次比较。

这里有个容易踩的坑：判断条件必须是arr[mid] <= arr[mid + 1]，不能写成arr[mid] < arr[mid + 1]。因为如果相等，虽然整个区间不一定严格有序，但合并后结果和现在是一样的（稳定性要求相等元素保持顺序），所以也可以跳过。用<=能多命中一些情况。

3.3 什么数据分布下这个优化最香

我总结了几种典型场景：

• 完全有序数组：每一层递归的每个区间都会命中，几乎退化成O(n)的检查，性能极佳。
• 近乎有序（少量逆序）：大部分区间命中，只有少数需要真正merge，提升明显。
• 完全随机：命中率低，收益接近零，但也没有明显损失。
• 完全逆序：几乎不命中，退化为普通归并。

所以这个优化是"有则大赚，无则不亏"的类型，没有理由不加。

4. 优化三：辅助数组的复用与内存布局

buffer的管理方式看似小事，实则对缓存友好度和内存分配开销影响很大。

4.1 为什么不要在merge里临时开数组

新手最常见的写法是在merge函数内部std::vector<int> temp(right - left + 1)，然后合并到temp再拷回。这种写法有两个问题。

第一，每次merge都要分配和释放内存。归并排序的merge调用次数是O(n)级别的（准确说是n-1次内部节点），意味着百万级数据要分配释放上百万次内存。malloc/free本身有开销，频繁分配还会造成内存碎片。

第二，临时数组的大小随区间变化，缓存局部性差。而如果用一个和原数组等大的buffer，每次merge只用到其中一段，内存访问模式更规整。

所以正确做法是：在排序开始前分配一个和原数组等大的buffer，整个排序过程复用这一个buffer。这就是前面代码里buffer作为参数传递的原因。

4.2 全局buffer vs 传参buffer的取舍

有人喜欢用全局或静态buffer，省得传参。我不推荐，原因有二：一是全局状态让函数不可重入，多线程环境下会出问题；二是隐藏了依赖关系，代码可读性下降。传参虽然多写几个字符，但清晰、安全。

如果确实在意传参开销，可以把buffer封装进一个排序类，作为成员变量。这样既避免了全局状态，又不用每次传参。对于性能敏感的库代码，这是个不错的折中。

4.3 一个容易被忽略的细节：拷贝回原数组

merge的最后一步是把buffer里的结果拷回arr。这一步很多人想省，觉得能不能直接在buffer里排完再整体拷一次。答案是：对于递归版不行，因为上层merge需要arr里是排好序的。但对于迭代版（自底向上），可以做到两个数组交替作为源和目标，最后判断结果在哪个数组里，省掉最后一次拷贝。这个后面讲迭代版时会展开。

拷贝本身可以用std::copy或者memcpy（对POD类型），比手写循环略快，因为标准库和编译器对它们有特殊优化。不过对于int这种简单类型，手写循环和memcpy差距很小，编译器基本能优化到一样。

5. 优化四：自底向上的迭代实现

递归版写起来直观，但递归有栈开销，而且深度受栈大小限制。迭代版（自底向上）从长度为1的子数组开始，两两合并，逐步扩大步长，完全消除递归。

5.1 迭代版的分层合并逻辑

迭代版的思路是：第一轮，把相邻的2个元素合并成有序的2元组；第二轮，把相邻的2元组合并成有序的4元组；以此类推，直到整个数组有序。

void mergeSortIterative(std::vector<int>& arr) { int n = arr.size(); if (n <= 1) return; std::vector<int> buffer(n); for (int width = 1; width < n; width *= 2) { for (int left = 0; left < n; left += 2 * width) { int mid = std::min(left + width - 1, n - 1); int right = std::min(left + 2 * width - 1, n - 1); if (mid < right) { mergeRange(arr, left, mid, right, buffer); } } } }

外层循环控制步长width，从1开始每次翻倍。内层循环按2width的间隔遍历数组，对每个区间做merge。注意mid和right都要用min防止越界，因为最后一段可能不足2width。

5.2 迭代版相比递归版的真实差异

迭代版的主要优势是消除了递归调用开销，对于超大数组（比如上亿元素）能避免栈溢出风险。但说实话，对于常规规模的数据，递归版和迭代版的性能差距很小，因为现代编译器对递归的优化已经不错，而且归并排序的递归深度只有log n，栈开销占比不高。

迭代版真正的价值在于可控性。你可以很方便地在迭代版里加入并行化——每一层的各个区间是相互独立的，可以并行merge。递归版做并行要复杂一些。另外迭代版更容易改造成原地归并或者外部排序。

不过迭代版有个小缺点：它不像递归版那样能自然地利用"小数组切换插入排序"的优化。你需要在第一层或者前几层手动处理。一个常见做法是先用插入排序把数组切成若干个长度为THRESHOLD的有序块，然后再从width=THRESHOLD开始迭代合并。

5.3 迭代版如何结合前面的优化

把插入排序和有序性检测都加进去：

void mergeSortIterativeOptimized(std::vector<int>& arr) { int n = arr.size(); if (n <= 1) return; std::vector<int> buffer(n); // 先用插入排序处理小块 for (int i = 0; i < n; i += INSERTION_THRESHOLD) { int right = std::min(i + INSERTION_THRESHOLD - 1, n - 1); insertionSort(arr, i, right); } // 从THRESHOLD开始迭代合并 for (int width = INSERTION_THRESHOLD; width < n; width *= 2) { for (int left = 0; left < n; left += 2 * width) { int mid = std::min(left + width - 1, n - 1); int right = std::min(left + 2 * width - 1, n - 1); if (mid < right && arr[mid] > arr[mid + 1]) { mergeRange(arr, left, mid, right, buffer); } } } }

这样迭代版也能享受小数组优化和有序性检测的好处。注意width的起始值变成了INSERTION_THRESHOLD，因为小于这个长度的块已经被插入排序处理好了。

6. 几个实战中踩过的坑

优化讲完了，但真正把这些代码用到项目里，还有一堆细节问题。这部分是我踩坑踩出来的经验，文档里一般不会写。

6.1 稳定性不是可有可无的

归并排序的一大卖点就是稳定。但如果你在merge时把arr[i] <= arr[j]写成arr[i] < arr[j]，稳定性就没了。对于排序int这种没有附属信息的类型，稳定性无所谓；但如果你排的是结构体，按某个字段排序，同时希望相等元素的原有顺序保留，稳定性就至关重要。

我见过一个真实场景：按分数排序学生列表，分数相同的学生要保持原来的学号顺序。用不稳定的排序，结果每次跑出来顺序都不一样，排查了半天才发现是merge的比较符号写错了。所以除非你明确不需要稳定性，否则老老实实用<=。

6.2 整数溢出与边界条件

前面提过mid = left + (right - left) / 2防溢出。还有一个容易错的地方是迭代版里的left + 2 * width - 1，当width很大时这个表达式可能溢出int。对于超大数组，建议用long long或者提前判断。虽然实际项目中很少排上亿个int，但库代码要考虑周全。

另外，空数组和单元素数组要提前返回，否则迭代版里width < n在n=0时直接不进循环，倒也没事，但递归版如果不判断left >= right会无限递归。这些边界都要测。

6.3 什么时候不该用归并排序

归并排序不是万能的。它的空间复杂度是O(n)，需要额外一个等大的buffer。如果你内存紧张，或者数据量小到几十个元素，插入排序或选择排序可能更合适。如果数据基本有序，插入排序甚至能到O(n)。如果对最坏情况性能不敏感、但要求原地排序，快排是更好的选择。

归并排序真正的优势场景是：需要稳定排序、数据量大、对最坏情况O(n log n)有要求、或者需要外部排序（数据大到内存放不下）。外部排序是归并排序的杀手锏，因为它的合并过程天然适合处理磁盘上的多个有序文件。

6.4 编译器优化等级对性能的影响

同一份代码，-O0和-O2编译出来的性能可能差好几倍。归并排序里大量的循环和数组访问，对编译器优化非常敏感。测试性能时一定要开优化，否则测出来的数据没有参考价值。我一般用-O2，追求极致可以试-O3，但要注意-O3有时会因为过度优化导致代码膨胀，反而变慢，得实测。

另外，-march=native能让编译器针对当前CPU生成更优的指令（比如SIMD），对数组操作有加速效果。但这样编译出的二进制不能跨机器用，发布版本要谨慎。

7. 完整可运行的最终版本

把前面所有优化整合到一起，给一份完整的、可以直接编译运行的代码。这份代码包含递归版和迭代版两个入口，都带优化。

#include <vector> #include <algorithm> #include <cstddef> const int INSERTION_THRESHOLD = 16; static void insertionSort(std::vector<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; } } static void mergeRange(std::vector<int>& arr, int left, int mid, int right, std::vector<int>& buffer) { int i = left, j = mid + 1, k = left; while (i <= mid && j <= right) { buffer[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; } while (i <= mid) buffer[k++] = arr[i++]; while (j <= right) buffer[k++] = arr[j++]; for (int p = left; p <= right; ++p) arr[p] = buffer[p]; } static void mergeSortRec(std::vector<int>& arr, int left, int right, std::vector<int>& buffer) { if (right - left + 1 <= INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } int mid = left + (right - left) / 2; mergeSortRec(arr, left, mid, buffer); mergeSortRec(arr, mid + 1, right, buffer); if (arr[mid] <= arr[mid + 1]) return; mergeRange(arr, left, mid, right, buffer); } void mergeSort(std::vector<int>& arr) { if (arr.size() <= 1) return; std::vector<int> buffer(arr.size()); mergeSortRec(arr, 0, static_cast<int>(arr.size()) - 1, buffer); } void mergeSortIterative(std::vector<int>& arr) { int n = static_cast<int>(arr.size()); if (n <= 1) return; std::vector<int> buffer(n); for (int i = 0; i < n; i += INSERTION_THRESHOLD) { int right = std::min(i + INSERTION_THRESHOLD - 1, n - 1); insertionSort(arr, i, right); } for (int width = INSERTION_THRESHOLD; width < n; width *= 2) { for (int left = 0; left < n; left += 2 * width) { int mid = std::min(left + width - 1, n - 1); int right = std::min(left + 2 * width - 1, n - 1); if (mid < right && arr[mid] > arr[mid + 1]) { mergeRange(arr, left, mid, right, buffer); } } } }

这份代码我用了很久，在各种数据规模和分布下都测过，稳定性、正确性、性能都靠谱。你可以直接拿去用，也可以根据自己的场景调整阈值。

最后分享一个我个人的习惯：每次写完排序，我都会用一组包含重复元素、已排序、逆序、随机、单元素、空数组的测试用例跑一遍，确认结果和std::sort一致。这个习惯帮我抓出过好几次边界bug，尤其是迭代版里那些min的边界处理。排序算法看着简单，但细节魔鬼，多测几组数据永远不亏。