我一直觉得，递归与分治策略这几个字，光看定义是看不出威力的。直到我把归并排序和堆排序连着看了好几遍，又被问过几次“为什么这两个算法经常放在一起讲”，我才慢慢琢磨明白：分治解决的是“怎么拆问题”，递归解决的是“怎么把拆开的问题做到底”，而归并排序和堆排序恰好把这套逻辑用两种完全不同的方式展示出来了。这篇文章我把它们放到一起复盘，从实现细节、复杂度分析到工程里的场景取舍，一次性写清楚。不管你是准备面试，还是想在项目里把排序用明白，应该都能找到点想看的东西。

1. 两个算法给我的第一个共同印象：问题都能“递归地”变小

1.1 分治是拆解问题的策略，递归是执行策略的手段

很多人把“递归”和“分治”当成同一个东西，其实不是。分治是一种策略，它要求你回答三个问题：问题能不能拆成更小的同类问题？拆完之后子问题能不能独立解决？子问题的解能不能合并回原问题的解？归并排序对这三个问题的回答非常工整：把一个数组从中间切成两半，左半边排序，右半边排序，再把两个有序段合并成一个有序段。递归在这里扮演的角色，只是“分治策略”最自然的翻译方式——每次函数调用都在处理一个规模减半的同类问题。

堆排序看起来不太像分治，因为它的外层是一个迭代循环，并没有显式的“切分-合并”动作。但它的核心操作 maxHeapify 本身就是一个天然递归的过程：先判断当前节点是否满足堆性质，如果不满足，就把它和较大的孩子交换，然后递归地继续调整那个被破坏的子堆。每向下递归一层，关注的范围就缩小到一棵更小的子树。所以从“同一个处理规则递归地作用在缩小的问题上”这个角度看，堆排序和归并排序属于同一族思路，只是组织数据的方式完全不同。

1.2 排序问题本身就是递归结构最好的样本

数组排序很适合用来理解递归，因为它的子问题边界非常清楚。对长度为 n 的数组排序，可以变成“对左半个数组排序、对右半个数组排序、把结果合并”。对堆来说，则是“保证某个子树是堆、递归处理它的子子树”。这不是偶然，因为排序天然具有可分解性：局部有序可以组合成全局有序，局部满足堆性质也可以组合成全局满足堆性质。

我在学习阶段的体会是，不要只背归并排序和堆排序的代码，那样过两周就忘。要刻意问自己一句：每一层递归到底在保证什么？归并里，递归返回值是“这段区间已经有序了”；堆排序里，递归返回值是“以这个节点为根的子树已经满足堆性质了”。一旦把这条主线抓住，后面的边界条件和细节错误基本都能自己排查出来。

2. 归并排序的分治全流程：从递归树到 merge 实现

2.1 分解、解决、合并，每一步到底在做什么

归并排序的代码结构，是所有分治算法里最直白的一个，核心就三个动作。

• 分解：把区间[left, right]从中间一分为二，即mid = left + (right - left) / 2。
• 解决：递归地对[left, mid]和[mid + 1, right]分别排序。当区间只剩一个元素时，它天然有序，递归终止。
• 合并：把两个已经各自有序的区间，合并成一个大的有序区间。

这里最反直觉的地方是：真正的比较和移动全部发生在合并阶段，而不是分解阶段。分解只改变下标，不改变数据。可以类比成整理一手扑克牌：你先把牌分成两堆，每堆内部排好序，然后每次从两堆顶部各取一张最小的牌比较，把更小的那张放入结果中。整个过程不断重复，直到两堆都为空。

我见过不少人把归并排序写成这样：先 merge，再对左右递归排序。这在顺序上是错的。分治要求我们先让左右两边本身有序，然后合并才有意义；如果先合并，左右两边还是乱序，合出来的结果也是乱的。

2.2 merge 的边界处理与哨兵写法

merge 是归并排序里唯一有技巧的部分，它的任务是合并两个有序区间。常规写法是用两个指针i和j分别指向左半段和右半段，每次比较当前元素，把更小的放入原数组，然后移动对应指针。

void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int L[n1], R[n2]; for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) { arr[k++] = L[i++]; } while (j < n2) { arr[k++] = R[j++]; } }

上面这段代码，k从left开始而不是从 0 开始，是因为我们合并的是arr的某个子区间，不是整个数组。这个细节看着简单，实际写错的人非常多。

还有一种经典的哨兵写法，在L和R的末尾放一个“无穷大”值，这样就不用在循环里判断i < n1 && j < n2了，因为当某一边遍历完，哨兵值一定大于另一边剩余的元素，循环会继续把另一边的元素写回去。

void merge_with_sentinel(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int L[n1 + 1], R[n2 + 1]; for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } L[n1] = 2147483647; R[n2] = 2147483647; int i = 0, j = 0; for (int k = left; k <= right; k++) { if (L[i] <= R[j]) { arr[k] = L[i++]; } else { arr[k] = R[j++]; } } }

哨兵写法的好处是省掉两个收尾循环，代码看起来更紧凑。但它有个潜在前提：数据本身不会达到INT_MAX这个值，否则哨兵会和真实数据混淆，可能导致排序结果不正确。实际工程里我倾向用普通写法，正确性更直观，也方便调试时看边界条件。哨兵写法更适合个人练习和对性能极致抠细节时使用。

2.3 递归树的高度只有 O(log n)，每一层总操作量是 n

归并排序为什么稳定是 O(n log n)？用递归树看非常清楚。

假设数组长度是 8，第一层有一个规模为 8 的问题，第二层有两个规模为 4 的问题，第三层有四个规模为 2 的问题，第四层有八个规模为 1 的问题。每一层的所有子问题加起来，规模总和都是 8。每一层要做多少合并工作？合并两个总长度为 m 的有序区间，需要处理 m 次比较和拷贝，所以这一层的总工作量是 O(n)。

递归树高多少？从规模 n 降到 1，每次除以 2，最终高度是 log2(n) 的级别。所以总时间复杂度就是 O(n log n)。

第 0 层： 8 第 1 层： 4 4 第 2 层： 2 2 2 2 第 3 层： 1 1 1 1 1 1 1 1

这个递归树结构还解释了另一个事：递归调用栈的深度只有 O(log n)，不会像某些递归写法那样发生栈溢出。理论上处理任意大规模数据，归并排序的递归深度都很可控。这也是它在外部排序里能被当成基础算法的原因之一——递归深度低，合并逻辑又是纯顺序访问，对磁盘和文件系统都友好。

2.4 自底向上的迭代版归并

分治策略不一定非要用递归实现，也可以用迭代从底层做起。自底向上的归并排序思路是：先把数组看成一个个长度为 1 的有序块，然后相邻两块两两合并成长度为 2 的有序块，再合并成长度为 4 的有序块，直到整个数组有序。

void mergeSortBottomUp(int arr[], int n) { for (int width = 1; width < n; width *= 2) { for (int left = 0; left < n; left += 2 * width) { int mid = left + width - 1; if (mid >= n - 1) { continue; } int right = left + 2 * width - 1; if (right >= n) { right = n - 1; } merge(arr, left, mid, right); } } }

这段代码里有个容易忽略的点：当右半段不存在时，也就是mid >= n - 1，这一轮不需要合并。另外，最后一个块的right可能超出数组末尾，必须取n - 1。迭代版归并最大的优势是省掉了递归调用，接近标准库函数的使用习惯；它也是理解外部排序里“多路归并”概念的前置知识。实际物理内存中数据无法一次性载入时，你做的就是这种分块排序加归并的思路。

3. 堆排序：藏在数组里的完全二叉树

3.1 用数组下标表达完全二叉树的父子关系

堆排序不是靠“切分数组”来分治，而是靠“堆”这种数据结构。堆本质上是一棵完全二叉树，所谓完全二叉树，是指除了最后一层之外每一层都是满的，最后一层也尽可能左对齐。这种结构有一个巨大的好处：可以用数组紧凑存储，不需要指针。

如果用 0-based 下标存储，那么对于一个下标为i的节点：

• 父节点下标是(i - 1) / 2
• 左孩子下标是2 * i + 1
• 右孩子下标是2 * i + 2

最大堆的性质是：每个节点的值都不小于它的孩子节点。也就是说，堆顶元素一定是全局最大值。你不需要维护整个数组完全有序，但你要保证这个“局部大于”的性质成立。这个性质维护起来非常便宜，调整一次只需要沿着一条路径下沉，代价 O(log n)。

3.2 建堆为什么从最后一个非叶子节点往上调整

建堆是堆排序第一个容易写错的步骤。先给出代码，再解释为什么。

void buildMaxHeap(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { maxHeapify(arr, n, i); } }

关键问题是：为什么从n / 2 - 1开始，而不是从n - 1开始，也不是从 0 开始？因为下标从n / 2到n - 1的节点全是叶子节点。叶子节点没有孩子，天然满足最大堆性质，不需要调整。从它们上面开始，倒着往根调整，才符合“先保证下面的子树已经是堆，再处理父节点”的逻辑。

如果从根开始往下调整，那么当前节点的左子树和右子树可能还没有满足堆性质，你把根下沉到某个孩子位置后，并不能保证下沉路径上的所有子树都正确。自底向上的建堆，保证maxHeapify被执行时，被处理节点的两个孩子都已经各自是堆，因此一次下沉就能让以该节点为根的整棵子树变成堆。

maxHeapify的实现如下：

void maxHeapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; maxHeapify(arr, n, largest); } }

注意maxHeapify中所有比较都有< n这样的边界限制，因为当前的“有效堆大小”并不一定等于原数组长度。这个n是参数，很容易被忽略。

3.3 排序循环：交换堆顶、缩小堆、再下沉

建好最大堆之后，数组中的最大值已经在arr[0]。堆排序的主体循环做的事情非常机械：

• 把arr[0]和当前堆的最后一个元素交换，这样最大值被“固定”到数组末尾。
• 把有效堆大小减一，因为末尾已经排好，不再参与后续调整。
• 对根节点arr[0]调用maxHeapify，恢复最大堆性质。

每轮循环之后，数组末尾就会多一个排好序的最大值，随着 i 从 n-1 递减到 1，整个数组完成升序排序。

void heapSort(int arr[], int n) { buildMaxHeap(arr, n); for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; maxHeapify(arr, i, 0); } }

这里面最容易被忽略的是maxHeapify(arr, i, 0)中的i。它表示当前有效堆的大小。如果写成maxHeapify(arr, n, 0)，每一轮都会把已经排到末尾的最大值重新拉回堆顶比较，排序结果会乱。这类 bug 非常阴险，因为小规模数据测试时可能碰巧没错，数据稍大就暴露。

堆排序的时间复杂度是 O(n log n)。建堆过程看起来要循环 n/2 次，每次调 maxHeapify 需要 O(log n)，直觉上像是 O(n log n)，但通过摊还分析可以证明建堆的真实复杂度是 O(n)，因为越靠近底层的节点高度越小，需要调整的路径长度很短。真正的 O(n log n) 消耗出现在后面的 n-1 轮交换和下沉中。

4. 归并与堆排序的“性格”差异：稳定性、空间与常数因子

4.1 稳定性：归并稳定，堆排序不稳定

“稳定性”是一个看起来不太起眼、实际非常重要的性质。如果数组里有两个相等的元素5a和5b，排序后5a仍然出现在5b前面，我们称这个排序是稳定的。

归并排序的稳定性来自 merge 阶段的比较规则：当L[i] <= R[j]时，我们先取左半段的元素。也就是说，两个相等元素相遇时，左半段那个会被优先放回原数组，所以相对顺序被保留。这一点在工程里很重要，比如你先按姓名排序，再按部门排序，稳定排序能让第二次排序后部门相同的人仍然按姓名有序。

堆排序则不稳定。原因在于它会把堆顶元素直接交换到数组末尾，这种“跨越”式的交换可能把相同元素的相对顺序打乱。举一个简单的例子：数组[5a, 3, 5b, 1]，建堆过程中你很难保证两个 5 的相对位置不发生颠倒。所以如果你需要保持相等元素原有顺序，堆排序直接出局。

4.2 空间：归并需要 O(n)，堆排序原地完成

归并排序的标准实现需要额外一个和原数组等长的辅助数组，用来在 merge 阶段暂存数据。这意味着空间复杂度 O(n)。如果对这个额外空间有要求，比如在内存受限的嵌入式环境里处理几千万条记录，O(n) 辅助空间可能是不可接受的。

堆排序的空间复杂度是 O(1)，它只需要少量临时变量，所有操作都在原数组上完成。这是堆排序最大的现实优势。当然，如果考虑递归实现版本，maxHeapify的递归调用会有 O(log n) 的栈空间，但相比归并的 O(n) 辅助数组，已经轻量太多了。

不过“原地”并不代表“更快”，涉及到 CPU 缓存和内存访问模式时，事情会更复杂，下面单独说。

4.3 常数因子：为什么堆排序“赢了复杂度，输了实测”

理论上归并排序和堆排序都是 O(n log n)，但在绝大多数真实数据上，归并排序往往跑得比堆排序快，快排又往往比归并快。问题出在常数因子和缓存局部性。

堆排序的调整过程会频繁访问2*i+1和2*i+2这两个下标，它们之间通常不是连续内存，跳跃访问会对 CPU 缓存不友好。而且每次 maxHeapify 至少涉及父节点和两个孩子的比较，比较次数相对较多。归并排序则是把元素连续地拷贝到辅助数组、再连续地写回原数组，内存访问模式非常线性，现代 CPU 的预取机制可以“猜到”下一步访问哪里。所以同样是 O(n log n)，实际耗时差距可能很大。

我做一个不完全严谨的直观对比，在随机生成的 100 万个整数上各跑一次，大致是：

这不是说堆排序一无是处。当内存严格受限、或者你并不需要一个通用排序而只是想快速拿到最大几个元素时，堆仍然是最好的选择。它不是一个糟糕的排序方案，但它的价值更多体现在数据结构本身，而不是作为通用排序器。

5. 实战中我踩过的坑和调试方案

5.1 归并排序的三个经典边界问题

第一个坑是递归终止条件写成if (left > right)。归并排序把区间拆成[left, mid]和[mid+1, right]，当 left 等于 right 时区间已经只有一个元素，应该返回。如果等号处理不好，可能无限递归或者多递归一层，导致索引越界。正确写法是if (left >= right)。

第二个坑是合并时指针k的起点。前面提到过，k必须从left开始，有的人从 0 开始写，结果排序完只有一小段正确。这个小 bug 用脑内模拟一遍就能发现，但当你疲劳赶工时非常容易写错。

第三个坑是求mid时写成(left + right) / 2。当 left 和 right 都很大时，这个表达式可能整型溢出。虽然现在多数机器上 int 溢出后计算结果未必立刻崩，但排序结果会莫名其妙错误。写left + (right - left) / 2是一个值得坚持的好习惯。

5.2 堆排序里最容易翻车的三处

第一处是父子下标换算混用。教材里很常用 1-based 下标，父节点是i/2，孩子是2i和2i+1。一旦你照抄到 0-based 数组里，就会写出left = 2 * i而不是2 * i + 1，数组越界或者访问错位几乎是一定的。

第二处是maxHeapify里的n没有跟着有效堆大小走。排序主循环每轮都缩小堆，如果不把当前堆大小传进去，“已经排出”的末尾元素会被再次当作堆内元素参与调整，已经排好的部分会被重新打乱。

第三处是建堆循环的起点。从n/2 - 1开始是正确的；从n/2开始通常会多一次无效调用，问题不大；从n-1开始会出现一堆无意义的叶子调整，性能变差但结果也许没错；真正错误的是从 0 开始正序遍历，因为子树还没建好，堆性质不可能正确建立起来。

5.3 让算法“可观测”的调试方法

我会给每个排序算法配一个小的“验证器”，排序后立刻扫描一遍，看是否非降序：

int isSorted(int arr[], int n) { for (int i = 1; i < n; i++) { if (arr[i - 1] > arr[i]) { return 0; } } return 1; }

在验证器之外，还建议准备四组测试数据：完全随机数组、已经升序的数组、已经降序的数组、所有元素都相同的数组。很多排序 bug 只会在某一种数据上暴露。比如归并排序在逆序数据上通常没问题，但堆排序如果建堆起点写错，逆序数组最容易发现异常。

更直观的办法是打印中间状态。归并排序可以打印递归拆分的过程，观察每一层的区间范围；堆排序可以打印每轮交换堆顶后的数组内容，看末尾是否逐次固定最大值。这个做法比较笨，但非常有效。我在调试一个排序工具时，就是靠打印一轮堆调整后的数组，才抓到有效堆大小没传对的问题。

6. 工程场景里到底该怎么选，以及我的一些经验体会

6.1 归并排序的现实用途：外部排序与链表排序

通用排序大家都默认用标准库里的排序函数，因为它是各种优化技巧打磨过的结果，比如把快排、插入排序、堆排序混合使用。但归并排序有两个真实场景很难被替代。

第一个是外部排序。当数据量大到没法一次性装入内存，你需要把大文件切成多个小片段，每个片段分别读入内存排好序写回磁盘，最后把所有有序片段做多路归并。归并的过程天然适合顺序读写，不需要随机访问，这对磁盘和网络文件系统都友好。我曾在模拟项目X里处理超过内存容量的日志数据，核心思路就是分块排序加归并，整个过程稳定可控。

第二个是链表排序。链表的节点分散在内存中，快排的随机访问和堆排序的下标访问都不好用，而归并排序对链表非常自然：先把链表切分成两半，递归排序，再把两个有序链表按指针接起来，完全不需要额外数组，空间开销可以做到 O(1)。所以很多语言标准库在排序某些特定容器时会选用归并思路。

6.2 堆排序的真正价值：优先队列、TopK 和时间管理

在通用排序里，堆排序不是第一选择。但“堆”这个数据结构本身无处不在。

你只需要快速拿到当前最大或最小的元素，用一个最大堆或最小堆就够了。任务调度器要每次取出优先级最高的任务，本质上就是堆的操作；找一批数据里最大的 K 个元素，维护一个大小为 K 的最小堆，每次遇到比堆顶大的元素就替换并调整，一趟扫描下来结果就出来了，不需要全量排序；流式数据的中位数，也可以用两个堆来维护。

所以我的建议是：不要只把堆排序当成一个排序算法去背，而是当成二叉堆的入门操作来学。你会真正受益的是建堆、调整、下称这些动作本身，而不是那 n 次交换堆顶的排序步骤。

6.3 一个不严谨但直观的实测印象

我在本地对随机整数数组做过简单测试，规模从 10 万到 100 万不等，印象最深的是：在接近有序的数据上，库函数排序往往非常快，归并排序得益于合并时对有序子段的利用也不差，堆排序则是无论数据是否有序，时间都差不多。堆排序的综合表现几乎总是比归并和快排慢一些。

这不是说堆排序理论复杂度骗人，而是复杂度分析丢掉了常数和局部性。它提醒我，在算法选型时不能只看大 O。如果内存充足、要求稳定，归并更好；如果内存很紧、只需要部分有序信息，堆更好；如果没有任何特殊约束，优先相信标准库的排序函数。

6.4 递归与分治给我留下的两点体会

第一点体会是：递归的难点不在于“调用自己”，而在于你要准确描述“规模更小的子问题”和“子问题之间如何组合”。归并排序能写对，是因为你只需要相信两句话：左半边排好，右半边排好，然后一合并，整个区间就排好了。这种“相信递归”的思维方式在后续处理树、图、区间问题时会反复用到。

第二点体会是：算法复杂度看总量，工程实现看细节。堆排序和归并排序的渐近复杂度相同，可实际表现差距很大；同样一个归并，辅助数组分配方式不同、边界处理不同，性能也能差出一大截。多跑测试、多打印状态，比空想复杂度更容易发现真正的瓶颈。

最后分享一个小技巧：如果你在写递归类算法时总觉得哪里不对，先在纸上画一棵规模为 8 的递归树，手动模拟两层，然后把每一层“应该返回什么”写在边上。归并排序返回有序数组段，堆调整返回满足堆性质的子树。这比直接单步调试更快，也能帮你绕过很多隐蔽的边界问题。