聊排序算法绕不开递归与分治，而递归与分治策略里最值得反复琢磨的两个代表，就是归并排序和堆排序。我在日常开发里很少会为了“排序而排序”，但一旦需要手写底层组件、处理几十万条日志、或者在面试现场写一段稳定的排序代码，这两类排序总会第一个出现在脑子里。这篇文章不止讲算法步骤，还会把复杂度的直觉推导、边界条件的坑、稳定性带来的业务影响，以及我实际调试时踩过的细节一起写出来。想彻底搞懂递归、想弄明白为什么归并排序稳定而堆排序不稳定、想写出一次跑通的排序代码的人，都可以按这条线过一遍。

1. 递归与分治：先把“拆”和“合”想清楚

1.1 分治三步曲：拆、解、合

分治策略的核心思想其实就六个字：拆、解、合。把一个规模较大的问题拆成若干个规模较小的子问题，子问题继续拆，直到小到可以直接解决；然后从最小的问题开始，逐层把答案合并回完整答案。这里的“递归”不是玄学，而是一种“我假设子问题已经有人帮我解决了，我只负责把当前问题处理好”的思维方式。

拿整理一叠乱序试卷举例。你不会一张一张地从头调整到最后，而是先把试卷分成两半，让两个人各自整理；如果每一半还是太多，就继续分下去，直到每个人手里只有一两张，随手就能排好。最后再把两摞已经有序的试卷按顺序合并成一摞。这个场景里，“拆”就是分段，“解”就是在小段上排序，“合”就是把有序段合并。归并排序完全复刻了这个过程，只不过把“排试卷”变成了对数组排序。

之所以要这样设计，是因为排序的最基本操作是“比较两个元素的大小”。如果直接在原始数组上做逐位调整，一次比较往往只能消除一个逆序对；而分治把数组拆成两半，分别排好后再合并，一次合并就能同时处理一大片逆序关系，整体效率自然上去了。

1.2 递归必须想清楚的终止条件

写递归最怕的不是递归本身，而是“不知道什么时候该停”。归并排序的递归终止条件非常干脆：当待排序区间里没有元素，或者只剩一个元素时，直接返回。

我见过不少初学者写递归排序时，把边界写成left < right才递归，然后又写了mid = (left + right) // 2，结果在数组长度为 2 时左半区是空区间，右半区是原区间，递归永远不会到终止条件，最终栈溢出。真正稳定的写法是左闭右闭区间[left, right]，当left >= right时说明区间为空或只有一个元素，不需要再处理。

递归的深度也需要心里有数。归并排序每次把区间一分为二，深度是 O(log n)，即使处理一百万条数据，递归栈深度也只有二十层左右，完全不用担心栈溢出。但堆排序中的heapify如果用递归实现，它的深度取决于堆的高度，同样是 O(log n)，也不会有栈压力。真正需要警惕的是那些每层只减少一个元素的递归场景，比如朴素快排在最坏情况下会递归 n 层，那种情况下栈溢出才是真实风险。

1.3 从递归树直观理解 O(n log n)

很多人把 O(n log n) 当作需要背下来的结论，其实从递归树上一眼就能看出来。归并排序每一层递归做的事情是：把所有子区间两两合并，合并一个长度为 m 的区间大约需要比较和复制 m 次。整个数组长度是 n，同层所有子区间长度加起来就是 n，所以每一层的合并总耗时是 O(n)。

递归树的深度是 log n 层，因为每次规模减半，从 n 到 1 需要 log n 次。每层 O(n)，总耗时就是 O(n log n)。这个推导方式比硬记公式实用得多，因为它能解释“为什么归并排序无论输入好坏都是 O(n log n)”——因为拆分总是对半分的，合并总是完整跑一遍，不存在快速排序那种“每次选到最差 pivot”导致递归树退化成一条直线的情况。

分治策略到这里埋下了一个关键伏笔：递归树每层的工作量是否均衡，直接决定算法能否保持 O(n log n)。归并排序的合并每层工作量都是 n，所以稳定；后面要讲的堆排序依靠的则是完全二叉树的层高，本质上也是 O(log n) 层，每层调整代价有界，整体也就不会退化。

2. 归并排序：最值得逐行手写的排序

2.1 整体流程：拆到不能再拆，再两两合并

归并排序的实现思路可以拆成两个阶段。第一个阶段是“递归分解”，把数组从中间一分为二，再分别对左右两半做同样的操作；第二个阶段是“合并”，把两个已经排好序的子数组合并成一个有序数组。

用数组[38, 27, 43, 3, 9, 82, 10]看一遍过程。第一次分解，中点在第 3 个元素附近，分成[38, 27, 43, 3]和[9, 82, 10]。继续分解，直到得到单个元素的区间，例如[38]、[27]、[43]、[3]等。合并时先从[38]和[27]开始，得到[27, 38]；[43]和[3]合并成[3, 43]；接着把[27, 38]和[3, 43]合并成[3, 27, 38, 43]。右侧同理，最后合并整个数组。

这里有个容易忽略的细节：合并两个有序数组时，每次比较两个子数组的头部元素，把较小的那个放入结果。因为左右两个子数组都已经有序，所以头部的其中一个一定是全局最小值。每次放入一个元素，指针向后移动，直到某个子数组被取完，再把另一个子数组剩余部分直接接上。

2.2 核心代码：用一份临时数组完成合并

归并排序的“合”是整个算法的核心，代码层面最大的难点不是递归，而是合并时临时数组的管理。最直观的写法是每次合并都新建一个数组，但这样会产生大量对象分配，在数据量大时性能很难看。我习惯在递归入口创建一份与原始数组等长的临时数组，合并时直接往临时数组对应位置写值，再拷贝回原数组。

def merge_sort(arr, left, right, tmp): if left >= right: return mid = (left + right) // 2 merge_sort(arr, left, mid, tmp) merge_sort(arr, mid + 1, right, tmp) merge(arr, left, mid, right, tmp) def merge(arr, left, mid, right, tmp): i = left j = mid + 1 k = left while i <= mid and j <= right: if arr[i] <= arr[j]: tmp[k] = arr[i] i += 1 else: tmp[k] = arr[j] j += 1 k += 1 while i <= mid: tmp[k] = arr[i] i += 1 k += 1 while j <= right: tmp[k] = arr[j] j += 1 k += 1 for p in range(left, right + 1): arr[p] = tmp[p]

这里有三个边界点值得反复检查。

第一，mid的归属。左区是[left, mid]，右区是[mid + 1, right]，两区没有重叠也没有遗漏。如果写成mid - 1或mid偏移，就会漏元素或重复合并。

第二，两个while循环里<=和<的差别。上面这段代码用的是<=，也就是说左侧元素和右侧元素相等时，先取左侧，这样才能保证归并排序的稳定性。

第三，写回原数组时，tmp的下标不是从 0 开始，而是从left开始。很多人习惯临时数组下标从 0 开始，拷回去时才发现位置错位。最好的做法就是让tmp的下标与被合并区间的下标保持一致，省去换算的麻烦。

2.3 稳定性为什么重要：等于号写在哪一行

排序算法的“稳定”是指：两个相等的元素，排序后相对顺序与原始顺序保持一致。归并排序天然可以做到稳定，因为合并相等的两个元素时，只要确保先取左侧子数组的元素即可。也就是说，比较的时候用<=，而不是<。

如果某天你把if arr[i] <= arr[j]不小心改成了<，那么当左右两边元素相等时，会先取右侧元素，这样相对顺序就反了。看似无关紧要，但在业务上可能引发连锁反应。

举个例子。订单列表先按下单时间升序排列，然后要求按用户编号升序排列。如果第二趟排序是稳定的，那么相同用户编号的订单仍然保持下单时间顺序；如果第二趟排序不稳定，相同用户编号的订单时间顺序就可能被打乱。这就是为什么很多数据库排序、多关键字排序都偏爱稳定排序。

稳定性的代价也很清楚：归并排序需要额外 O(n) 的空间存临时数组，而且合并时要频繁读写临时数组和原数组，内存开销和拷贝耗时比原地排序高。换句话说，它是用空间换稳定和确定性。

2.4 归并排序的优化思路

工程上不会直接写一个朴素归并排序，通常会在几个点上做优化。

第一个优化是小数组改插入排序。当递归拆分到区间长度小于某个阈值时，比如 16 或者 32，直接使用插入排序，而不继续拆分。原因是递归调用本身有开销，小数组上的插入排序常数极低，实测往往比继续递归合并更快。这个阈值不要拍脑袋，最好在自己的数据规模上测一下，不同语言、不同编译器下的最优阈值会差不少。

第二个优化是复用临时数组。前面代码已经在递归入口创建了一份临时数组，避免每次合并都分配新数组。如果递归函数里写tmp = []然后tmp.append，在大数组上会有大量内存分配和垃圾回收压力。

第三个优化是判断是否需要合并。如果左子数组的最大值已经小于右子数组的最小值，说明两个子数组连接起来就已经有序，不需要执行合并。这个提前退出对“基本有序”的输入特别有效，能直接把部分递归树剪掉。

3. 堆排序：用数组模拟一棵完全二叉树

3.1 父子节点下标关系是堆的地基

堆排序的思路和归并排序完全不同。归并排序是靠“拆分后合并”逐渐排好序，堆排序则是先把数组调整成一个堆，利用堆顶最大或最小的性质，一次次把极值放到最终位置。

这里的“堆”是一棵完全二叉树，但它不是靠指针连起来的，而是直接存在数组里。数组下标天然映射了树的位置：根节点在位置 0；对于任意位置i，它的左孩子在2 * i + 1，右孩子在2 * i + 2，父节点在(i - 1) // 2。这个关系是整个堆排序的地基，任何一个下标算错，后面的操作都会连环出错。

我一开始从 C 语言式 1 下标切换到 0 下标时，老是把左孩子写成2 * i，然后就会访问到错误的位置。建议刚学的时候，不要贪快，先用小数组把下标关系列一遍，确认 0 下标下左孩子是 1、右孩子是 2，父节点是 0，后再写代码。

堆排序通常用大顶堆来做升序。大顶堆的意思是每个节点的值都大于等于它的子节点，因此堆顶一定是整个数组的最大值。排序时，先把数组建成大顶堆，然后把堆顶和数组末尾元素交换，最大元素就到了正确位置；接着缩小堆的有效范围，再调整剩下的堆，继续取最大值放到倒数第二个位置。重复下去，数组就有序了。

3.2 堆化：从最后一个非叶子节点开始

建堆的过程叫“堆化”或“下沉”。对某个节点，需要比较它和它的左右孩子，如果孩子比它大，就把孩子里更大的那个换上来，然后继续向下检查被换下去的那个节点，直到它不再比孩子小，或者到达叶子节点。

关键问题是：从哪个节点开始做下沉调整？答案是最后一个非叶子节点。在完全二叉树里，最后一个非叶子节点的下标是n // 2 - 1。从它开始，向前遍历到根节点，逐个做下沉调整，就能把整个数组建成堆。

为什么不用从叶子节点开始？因为叶子节点没有孩子，不存在“下沉”的必要。从最后一个非叶子节点开始，本质上是在后往前一层层建立堆，每个节点下沉时它的左右子树已经是大顶堆，所以只要处理当前节点这一个“入侵者”。

堆化的代码可以递归，也可以迭代。递归版本思路直观，迭代版本可以避免 Python 默认递归深度限制的担忧。下面是递归版本：

def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)

这里n是当前堆的有效长度，不是原始数组长度。每次递归调用时，largest变成了新的父节点，但n保持不变，因为堆的范围没有变。容易写错的地方是在递归调用里误把n改成了largest + 1之类的值，会出现数组越界。

3.3 排序主体：先建堆，再不断交换堆顶

有了heapify，堆排序的完整流程就很清晰了。

建堆：从n // 2 - 1开始，倒序执行heapify(arr, n, i)，直到i = 0。这一步做完，数组已经满足大顶堆性质，堆顶也就是arr[0]是最大值。

排序：从最后的下标i = n - 1开始，循环到i = 1。每轮把arr[i]和arr[0]交换，最大值被放到数组尾部；然后对当前缩减后的堆执行heapify(arr, i, 0)，重新调整堆顶。这里的i既是要交换的下标，也是下一轮堆的有效长度，含义要盯清楚。

def heap_sort(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0)

很多人在建堆后的交换阶段写错，是因为忽略了heapify的第二个参数。每一轮交换后，数组尾部的元素已经是排好序的，不应该再参与堆调整，所以必须把堆的有效长度缩小。这里的i正好就是新的有效长度，不能写成n。

3.4 堆排序的空间优势与固有短板

堆排序最大优势是原地排序，空间复杂度只有 O(1)。它不需要额外的临时数组，也不像递归归并那样需要维护递归栈。这一点在嵌入式、内存受限的环境里价值很高。

但堆排序也有一个常被忽略的短板：虽然时间复杂度和归并排序、快速排序一样是 O(n log n)，但实际运行常数通常比快速排序大。原因是堆排序对数组的访问模式是跳着访问的，i、2*i+1、2*i+2这些下标之间的关系让 CPU 缓存命中率远低于快速排序和归并排序的连续访问。再加上堆排序在建堆完成后，堆顶被拿出来放到末尾，然后又要下沉，每次下沉都比较几次，总的比较次数比快速排序多不少。

所以，工程上需要 O(1) 空间且不要求稳定时，堆排序可以上；如果内存够用且追求实际性能，归并排序通常更稳。堆排序更大的舞台其实是优先级队列、Top K 问题和调度器，这些问题只是借用“堆”这一数据结构，不是每次都要完整排序。

4. 实际开发中的选型与排错

4.1 归并排序的边界条件自查清单

我把归并排序常见的错误整理成一份清单，每次手写完后逐条检查，基本能一次跑通。

第一，检查递归终止条件。必须是left >= right返回，不能是left == right，否则空区间会进入死循环。

第二，检查mid的赋值。mid = (left + right) // 2，左区右端是mid，右区左端是mid + 1。如果数组下标写错，合并结果会乱。

第三，检查合并循环里的指针推进。两个主循环分别对应左区和右区，循环条件为i <= mid和j <= right。合并完一个数组后，另一个数组剩余部分必须复制进去，漏掉这个步骤会导致元素丢失。

第四，检查写回。临时数组下标和原数组下标要一致，写回要从left到right，不能从 0 开始。最稳妥的写法是合并时临时数组的下标也初始化为left，复制时直接全区间写回。

第五，检查稳定性。如果要求稳定，左边元素必须用<=比较，而不是<。可以在测试数据中加入重复元素，验证排序前后相同元素的相对位置。

4.2 堆排序的常见错误与调试方法

堆排序的坑比归并排序更隐蔽，因为肉眼很难从最终结果判断是哪一步出了问题。常见错误有几个。

最后一个非叶子节点算错：有人记成n // 2，有人记成(n - 1) // 2。正确是n // 2 - 1，原因是数组最后一个元素下标是n - 1，它的父节点是(n - 2) // 2，在 Python 整数除法下这个值等于n // 2 - 1。

heapify中孩子下标越界：判断left < n和right < n不能省略。堆排序过程中堆的有效长度不断缩小，如果直接用原始n，会把已经放到末尾的最大元素重新拉进堆里，排序结果错乱。

交换后忘记继续下沉：堆顶被交换上来一个较小元素后，必须对新的堆顶做heapify，否则不满足大顶堆性质，下一轮取值就会拿错。

调试堆排序时，我通常写一个打印函数，把数组按完全二叉树的结构缩进打印。这样能直观看到某个节点和左右孩子的关系，定位是哪一步的下沉出了问题。还可以在每次交换后打印数组，对照“末尾最值已经就位”和“前面仍然满足堆”两个条件逐步核对。

4.3 从排序到真实需求：逆序对、Top K、稳定性选型

排序算法真正有嚼劲的地方，是它们能灵活改造，解决比“排个序”更大的问题。

归并排序可以在合并阶段顺手统计逆序对。合并两个有序子数组时，如果右侧元素比左侧小，那么左侧从当前指针到mid的所有元素都比右侧这个元素大，这些元素与当前右侧元素都构成逆序对，数量直接增加mid - i + 1。这个技巧比暴力双重循环高效得多，时间复杂度还是 O(n log n)。

堆排序思想则可以解决 Top K 问题。比如要从一亿条日志里筛出访问量最大的 100 条，不需要把所有日志完整排序，只需要维护一个大小为 100 的小根堆，每个新元素与堆顶比较，比堆顶大就替换并下沉。最终堆里就是最大的 100 条，时间复杂度 O(n log k)，内存只有 O(k)。

稳定性选型同样落到业务上。前面提到多关键字排序场景，最好用稳定排序。而如果你只是要取一批数据里的最大值，堆排序的稳定性根本不重要，堆结构本身就够用。选型不要只盯复杂度表，还要看数据规模、内存限制和业务是否关心相同元素的相对顺序。

4.4 排序算法对比速查表

这张表不是用来背的，而是用来做决策的。如果业务数据量小且基本有序，插入排序反而最快；如果数据量巨大且内存充足，归并排序的稳定性和稳定复杂度最让人省心；如果内存受限且不关注稳定性，堆排序是安全选择；如果追求通用场景下的平均表现，工程库里的快速排序优化版本通常是首选。

5. 我写递归算法时的三个习惯

5.1 先信子问题，再写当前层

我在刚接触分治时，最大的心理障碍是递归展开时容易陷入细节，总想把每一步递归都推演完。后来养成了一个习惯：只关注当前这一层，并假设递归调用返回的子问题答案一定是正确的。这一步对归并排序尤其管用，写merge_sort(arr, left, mid, tmp)时，我心里默认左半区已经拍好序，不需要再问它是怎么排好的；同样，右半区也是。这样我就能把全部注意力放在merge的合并逻辑上。

这个习惯也可以推广到其他递归代码。先想清楚“这一层我要做什么”，再想清楚“我从子问题拿到什么样的输入”，最后补上终止条件。顺序不要反，否则容易在递归迷宫里出不来。

5.2 用最小用例把递归调用栈画出来

代码写完后，不要立刻跑大数据。我用一个四到六个元素的数组，把递归调用过程画在草稿纸上。归并排序就画分解和合并的层级；堆排序就画每个节点i下沉前后的堆结构。这种方式能发现很多肉眼看不到的问题，比如下标偏移一位、终止条件差一个位置、临时数组写回错位等。

画完之后，再跑几个极端的测试用例：空数组、只有一个元素、两个无序元素、所有元素相同、已经有序的数组。这些边界用例能最大限度暴露边界错误。

5.3 把稳定性写进测试用例里

最后分享一个检查稳定性的方法。准备一组带有唯一编号的对象，比如(编号, 成绩)，先用成绩排序，再验证相同成绩的编号顺序是否保持。这个测试最能区分归并排序和堆排序在实际业务中的差异。归并排序只要等于号正确，测试一定通过；堆排序如果要求稳定，则根本不满足条件，测试注定失败，这时你就知道该换方案了。

递归与分治策略并不是两个孤立的知识点。归并排序把分治的“拆解合并”做到了极致，堆排序则用数组上的树形结构配合递归调整换来了原地排序。弄懂这两个算法，你会更清楚“O(n log n)”到底是怎么来的，也会在真正面对大规模数据时，知道该为稳定性、空间、性能付出什么代价，又该在什么环节坚持自己的选择。