企业官网建设流程全解析

归并排序这个题目，我前前后后给人讲过不下二十遍，每次讲完都有人问同一个问题：递归版本我背下来了，可面试官让我手写非递归版本，脑子直接空白。这事儿其实不怪谁，大部分教材把归并排序讲成"分治思想的标准范例"，递归树一画，代码一贴，看着挺优雅，但真到要把它拆成迭代、要控制边界、要算清楚临时数组该开多大，才发现里面全是细节。这篇就把归并排序从递归到非递归彻底捋一遍，顺带把冒泡和选择这两个"看起来谁都会、写起来总出错"的排序也带上，凑成一套能直接拿去用的排序工具箱。

先说清楚这篇适合谁看。如果你是刚学数据结构、被递归绕晕的同学，前面几节会把"分"和"治"拆到每一步都能对上号；如果你是在准备面试、需要手写非递归归并的人，中间那节迭代实现和边界处理是重点；如果你只是想把几个基础排序的复杂度、稳定性、适用场景一次性搞清楚，后面的对比表格和踩坑记录可以直接抄。归并排序的核心关键词就几个：分治、递归、迭代、临时数组、稳定排序、O(n log n)，这几个词贯穿全文，看到它们就知道讲到哪了。

1. 归并排序到底在"归"什么

很多人背得下代码，却说不清归并排序的名字从哪来。其实"归"就是合并，把两个已经排好序的序列合成一个有序序列，这个过程叫归并（merge）；"归并排序"就是先把数组拆到不能再拆，再一层层合并回来。理解这一点，后面递归和非递归的区别就很好懂了——它们拆的方式不同，但合并的逻辑是同一套。

1.1 从"两个有序数组合并"这个最小问题说起

归并排序的全部难点，其实都压缩在一个很小的操作里：给你两个各自有序的数组，怎么合并成一个有序数组。这个操作想通了，归并排序就通了八成。做法很朴素：两个指针分别指向两个数组的开头，比较当前元素，谁小就把谁放进结果数组，然后那个指针往后走一格；某个数组走完了，把另一个剩下的整段接上去。

举个例子，左边是[1, 4, 7]，右边是[2, 3, 9]。指针 i 指 1，j 指 2，1 小，取 1，i 后移；比较 4 和 2，取 2，j 后移；比较 4 和 3，取 3；比较 4 和 9，取 4；比较 7 和 9，取 7；左边走完，把右边剩下的 9 接上，得到[1, 2, 3, 4, 7, 9]。整个过程每个元素只被访问一次，所以合并两个长度分别为 m 和 n 的有序数组，时间复杂度是 O(m+n)。

这里有个容易被忽略的点：合并需要额外的空间来放结果。这就是归并排序空间复杂度 O(n) 的根源，也是它和冒泡、选择这些"原地排序"最本质的区别。你在写代码时那个temp数组不是随便开的，它的大小直接决定了算法能不能跑对。

1.2 分治：把大数组拆成只剩一个元素

有了合并的能力，剩下的问题就是"怎么保证合并的两边都是有序的"。答案是把数组一直拆，拆到每个子数组只有一个元素为止——一个元素天然有序，这时候再两两合并，合并出来的还是有序的，一层层往上，整个数组就有序了。

这个"拆"的过程就是分治里的"分"。以[38, 27, 43, 3, 9, 82, 10]为例，第一层拆成[38, 27, 43, 3]和[9, 82, 10]，第二层继续拆成[38, 27]、[43, 3]、[9, 82]、[10]，第三层拆成单个元素。然后开始"治"：[38]和[27]合并成[27, 38]，[43]和[3]合并成[3, 43]，再合并成[3, 27, 38, 43]，右边同理得到[9, 10, 82]，最后两边合并成[3, 9, 10, 27, 38, 43, 82]。

拆的层数是多少？每次对半拆，拆到长度为 1，层数是 log₂n。每一层合并的总工作量是 O(n)（因为每层所有元素加起来正好是 n 个，每个被访问常数次）。所以总复杂度是 O(n log n)。这个推导比死记结论有用得多，面试时被问"为什么是 n log n"，你就从"层数 × 每层工作量"这个角度答，比背公式有说服力。

1.3 为什么归并排序是稳定的，这一点比想象中重要

稳定性指的是：两个相等的元素，排序后它们的相对顺序不变。归并排序是稳定的，关键在于合并时的比较逻辑——当左右两个元素相等时，我们取左边的。代码里体现为if (left[i] <= right[j])而不是<。这个=号就是稳定性的开关，很多人写代码时随手写成<，排序结果看着没错，但稳定性已经悄悄丢了。

稳定性在实际业务里不是学术概念。比如你有一批订单，先按金额排好序，现在要按时间再排一次，如果排序算法稳定，那么同一时间的订单里，金额的顺序还能保留；如果不稳定，之前那次排序就白做了。这就是为什么 Java 里Arrays.sort对对象数组用的是归并排序的变体（TimSort），而对基本类型数组用的是快排——基本类型没有"相等但不同个体"的概念，稳定性无所谓，快排更快更省空间。

2. 递归版归并排序：从框架到每一行代码

递归版是最贴合"分治"字面意思的写法，也是理解归并排序的起点。它的结构非常对称：先递归排左半，再递归排右半，最后合并。但对称的背后有几个坑，尤其是区间边界的开闭问题，写错一个下标就是死循环或者数组越界。

2.1 递归框架：先分后合的三段式

递归函数的设计遵循一个固定套路：明确函数的作用、确定终止条件、拆解成子问题。归并排序的递归函数mergeSort(arr, left, right)作用是"把 arr 从 left 到 right 这一段排好序"，注意这里是闭区间，left 和 right 都能取到。

终止条件是left >= right，也就是这一段只剩一个元素（或为空），天然有序，直接返回。拆解就是取中点mid = left + (right - left) / 2，递归排[left, mid]，递归排[mid+1, right]，然后合并这两段。

这里中点为什么写成left + (right - left) / 2而不是(left + right) / 2？因为后者在 left 和 right 都很大时可能整数溢出。虽然实际业务里数组下标很难大到溢出，但这是个体现基本功的细节，面试时写出来是加分项。

def merge_sort(arr, left, right): if left >= right: return mid = left + (right - left) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid + 1, right) merge(arr, left, mid, right)

这段框架本身没什么难度，难的是merge函数怎么写才不会出错。下面单独拆。

2.2 merge 函数的边界处理：临时数组开多大、下标怎么对

merge(arr, left, mid, right)要做的事是：把arr[left..mid]和arr[mid+1..right]这两段有序序列合并，结果放回arr[left..right]。最直观的写法是开两个临时数组分别拷贝左右两段，再合并回原数组。

左段长度是mid - left + 1，右段长度是right - mid。注意这两个长度公式，差一个 1 是很多人栽跟头的地方。因为 mid 属于左段，所以左段是left到mid闭区间，元素个数是mid - left + 1；右段从mid+1开始到right，个数是right - mid。

def merge(arr, left, mid, right): left_part = arr[left:mid+1] right_part = arr[mid+1:right+1] i = j = 0 k = left while i < len(left_part) and j < len(right_part): if left_part[i] <= right_part[j]: arr[k] = left_part[i] i += 1 else: arr[k] = right_part[j] j += 1 k += 1 while i < len(left_part): arr[k] = left_part[i] i += 1 k += 1 while j < len(right_part): arr[k] = right_part[j] j += 1 k += 1

这段代码里k从left开始而不是从 0 开始，是因为结果要写回原数组的对应位置。如果你习惯从 0 开始写，那最后还得整体搬移，多此一举还容易错。另外注意left_part[i] <= right_part[j]里的<=，这就是前面说的稳定性开关。

提示：Python 切片arr[left:mid+1]是左闭右开，所以右边界要写mid+1才能把mid取到。这个细节在 C++ 或 Java 里不存在（它们用循环拷贝），但用 Python 写的时候特别容易漏。

2.3 递归版的复杂度与调用栈开销

递归版归并排序的时间复杂度是 O(n log n)，空间复杂度是 O(n)，这个 O(n) 包含两部分：merge 时的临时数组 O(n)，以及递归调用栈的深度 O(log n)。因为 O(n) 主导，所以整体记作 O(n)。

递归深度是 log₂n，对于百万级数据大约是 20 层，栈开销可以忽略。但如果是千万级甚至更大，递归深度虽然还是 log 级别，但每层函数调用的开销累积起来也不小。这就是为什么有些场景下要用非递归版本——不是为了省那点栈空间，而是为了避开函数调用的开销，同时让代码在某些对递归不友好的环境里也能跑。

还有一个实际问题是：递归版在合并时反复创建临时数组，如果每层都 new 一个，内存分配和回收的开销会拖慢速度。优化做法是在最外层开一个和原数组等大的辅助数组，所有 merge 操作共用它，通过下标区分左右段。这个优化在非递归版本里几乎是必须的，因为非递归没有"每层新建"的自然结构。

3. 非递归归并排序：把递归树"压平"成循环

非递归版本是很多人卡壳的地方。递归版的分治是"从上往下拆"，非递归版反过来，是"从下往上合"——先两两合并长度为 1 的段，再合并长度为 2 的段，再合并长度为 4 的段，直到段长超过数组长度。这个思路叫自底向上（bottom-up）归并排序。

3.1 自底向上的核心：控制"段长"这个变量

递归版里，"拆到多小"是由递归终止条件隐式控制的；非递归版里，这个信息必须显式用一个变量表示，就是当前每段的长度width。初始width = 1，表示每个元素自成一派；每轮合并后width *= 2，直到width >= n结束。

每一轮里，我们要把数组按width切段，相邻两段合并。假设当前段长是width，那么第一段的起点是left，中点是left + width - 1，第二段的起点是left + width，终点是min(left + 2*width - 1, n-1)。注意终点要取 min，因为最后一段可能不够width长。

def merge_sort_iterative(arr): n = len(arr) temp = [0] * n width = 1 while width < n: left = 0 while left < n: mid = min(left + width - 1, n - 1) right = min(left + 2 * width - 1, n - 1) merge_with_temp(arr, temp, left, mid, right) left += 2 * width width *= 2

这段代码的骨架就是两层循环：外层控制段长翻倍，内层从左到右扫过整个数组，每次处理一对相邻段。mid和right都用 min 兜底，防止越界。这里mid的 min 其实在left + width - 1 >= n时才会触发，意味着这一段已经不足 width，那它右边就没有第二段了，此时mid和right都等于n-1，merge 一个空操作，不影响结果。

3.2 用同一个 temp 数组完成所有合并

非递归版最优雅的地方是：所有合并共用一个temp数组。merge_with_temp(arr, temp, left, mid, right)的做法是先把arr[left..right]整段拷到temp的对应位置，然后从temp的两段里取元素，写回arr。这样避免了每次合并都新建数组。

def merge_with_temp(arr, temp, left, mid, right): for k in range(left, right + 1): temp[k] = arr[k] i = left j = mid + 1 for k in range(left, right + 1): if i > mid: arr[k] = temp[j] j += 1 elif j > right: arr[k] = temp[i] i += 1 elif temp[i] <= temp[j]: arr[k] = temp[i] i += 1 else: arr[k] = temp[j] j += 1

这段代码里i > mid和j > right是两个"某一边已经取完"的判断，放在前面优先处理，避免在比较时访问越界。这种"先判空再比较"的写法比"比较完再判空"更安全，因为后者在一边取完后还会去访问那个越界的下标。

注意：temp数组必须开成和原数组等大，不能只开right - left + 1，因为不同轮的合并区间位置不同，共用一个大数组最省事。如果你非要按区间开，那就退化成递归版每层新建的思路了，失去了非递归的优势。

3.3 非递归版的边界陷阱：最后一段不够长怎么办

非递归版最容易出错的地方，就是数组长度不是 2 的幂的时候。比如长度 7 的数组，width = 4那一轮，第一对段是[0..3]和[4..6]，第二段只有 3 个元素，不够 4 个。这时候mid = 3，right = 6，merge 依然正确，因为 merge 只要求两段各自有序，不要求等长。

真正会出问题的是width比剩余元素还大的情况。比如width = 8，数组长度 7，那left = 0时mid = min(7, 6) = 6，right = min(15, 6) = 6，此时mid == right，第二段为空，merge 实际只处理了第一段，等于没合并。这种情况不会出错，但会浪费一次循环。更稳妥的写法是在内层循环里加一个判断：如果mid >= right，说明没有第二段，直接跳过。

if mid < right: merge_with_temp(arr, temp, left, mid, right)

加上这个判断，逻辑更清晰，也避免了无意义的拷贝。这个细节在教材里经常被省略，但自己写的时候不加，虽然结果对，但效率上打了折扣，而且调试时容易怀疑自己。

4. 冒泡与选择：两个"简单排序"里的不简单

归并排序讲完了，顺带把冒泡和选择带上，不是凑数，而是这三个排序放在一起对比，能把"稳定性""交换次数""适用场景"这几个概念讲透。冒泡和选择都是 O(n²) 的排序，但它们的性格完全不同：冒泡是"相邻交换、稳定、能提前退出"，选择是"跳跃交换、不稳定、交换次数最少"。

4.1 冒泡排序：那个"提前退出"的优化才是精髓

冒泡排序的基础版是两层循环，外层控制轮数，内层从头到尾比较相邻元素，逆序就交换。每轮结束，最大的元素"冒"到末尾。基础版无论数组是否有序都要跑满 n² 次比较，但加一个标志位就能优化：如果某一轮没有发生任何交换，说明数组已经有序，直接退出。

def bubble_sort(arr): n = len(arr) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break

这个优化在数组基本有序时效果惊人，最好情况能到 O(n)。但要注意，内层循环的上界是n - 1 - i，因为每轮之后末尾 i 个元素已经排好，不用再比。这个- i漏掉不影响正确性，但会多做无用功。

冒泡排序是稳定的，因为只有arr[j] > arr[j+1]才交换，相等时不交换，相对顺序保留。它的交换次数等于逆序对的数量，这个性质在某些统计场景里有用。

4.2 选择排序：交换次数最少，但不稳定

选择排序的思路是：每轮从未排序区间里找出最小值，和未排序区间的第一个元素交换。它的比较次数固定是 n(n-1)/2，无论数组是否有序，这点和冒泡不同。但它的交换次数最多只有 n-1 次，这是它最大的优势——当交换成本很高时（比如元素是很大的结构体），选择排序反而比冒泡划算。

def selection_sort(arr): n = len(arr) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i]

选择排序不稳定，原因就在那个交换上。比如[5a, 5b, 2]，第一轮找到最小值 2，和第一个 5a 交换，得到[2, 5b, 5a]，两个 5 的相对顺序变了。这个例子是讲稳定性时最经典的，记住它就能随时解释为什么选择排序不稳定。

4.3 三种排序放在一起看：什么时候用哪个

把归并、冒泡、选择放一张表里对比，很多模糊的认识会一下子清晰。

从表里能读出几个结论。第一，归并排序的时间复杂度在所有情况下都是 n log n，没有最坏退化，这是它比快排稳的地方；代价是 O(n) 空间。第二，冒泡的最好情况是 O(n)，但只有加了提前退出优化才成立，不加的话最好也是 O(n²)。第三，选择排序的比较次数固定，适合"比较便宜、交换昂贵"的场景，但稳定性没了。

实际选型时，数据量大且要求稳定，归并是首选；数据量小或者基本有序，冒泡的优化版够用；如果内存紧张又不在乎稳定性，选择排序的原地特性有优势。至于快排，它平均更快但最坏会退化到 O(n²)，不在这次讨论范围里，但心里要有这个坐标。

5. 手写时最容易翻车的几个点

代码看懂了和能默写出来是两回事。下面这几个坑，是我见过最多人栽的，每一个都对应着具体的错误现象，照着排查能省不少时间。

5.1 递归版的区间开闭混乱

最常见的错误是把mid算成(left + right) / 2之后，递归调用写成merge_sort(arr, left, mid - 1)和merge_sort(arr, mid, right)。这种写法本身也能工作（只要 merge 对应调整），但它和"mid 属于左段"的约定冲突，一旦 merge 里按[left..mid]和[mid+1..right]处理，就会漏元素或者重复处理。

判断自己有没有踩这个坑，看两个地方：递归调用的两个区间是否无缝拼接且不重叠，merge 里的左右段长度公式是否和递归调用一致。这两处必须严格对应，改一处就得改另一处。我的习惯是统一用"mid 属于左段"的约定，所有代码都按这个来，形成肌肉记忆就不会乱。

5.2 非递归版的 width 翻倍时机

非递归版里width *= 2的位置很关键。它必须在内层循环（扫完整个数组）结束之后，而不是内层循环里面。如果写在内层里，每处理一对段就翻倍，段长会失控。这个错误的现象是排序结果部分有序但整体乱，因为不同位置的段长不一致。

另一个相关错误是外层循环条件写成width <= n而不是width < n。当width == n时，整个数组作为一段，没有第二段可合并，这一轮是空转。虽然结果不受影响，但多跑一轮。写成width < n更准确。

5.3 稳定性被<和<=悄悄破坏

前面提过，merge 里相等时取左边才能保持稳定。但很多人写冒泡时也会犯类似的错：把arr[j] > arr[j+1]写成arr[j] >= arr[j+1]，相等也交换，稳定性就没了。这种错误特别隐蔽，因为排序结果看起来完全正确，只有用"带标记的相等元素"去测才能发现。

测试稳定性的方法很简单：给每个元素附上原始下标，排序后检查相等元素的原始下标是否递增。这个测试用例建议每个人都备一个，写完任何排序都跑一遍。

5.4 临时数组复用时的脏数据

非递归版共用 temp 数组时，如果某一轮 merge 的区间没有完全覆盖 temp 的对应位置，残留的旧数据可能被误读。不过按前面给的merge_with_temp写法，每次都会先把arr[left..right]完整拷到 temp，再从中读取，所以不会有脏数据问题。但如果你为了"优化"省略了拷贝、直接比较 arr 和 temp，就要格外小心下标的对应关系。

提示：调试归并排序时，在 merge 前后打印arr[left..right]和 temp 的对应片段，能快速定位是"分"错了还是"合"错了。分错了表现为递归区间不对，合错了表现为合并结果不是有序的。

6. 几个能直接拿去用的实测结论

代码跑通只是第一步，真正用起来还得知道它的脾气。下面这些结论来自实际跑 benchmark 和踩坑，不是理论推导，但和理论能对上。

6.1 数据规模多大时归并开始明显快过冒泡

理论上归并是 n log n，冒泡是 n²，交叉点大概在 n 几十到一百之间。实测下来，Python 里 n=100 时两者差不多，n=1000 时归并快一个数量级，n=10000 时差距拉到两个数量级以上。但这个对比意义有限，因为 Python 的sorted用的是 TimSort，比手写归并快得多。手写排序的价值在于理解原理和应对面试，生产环境该用内置的就用内置的。

真正有参考价值的是递归版和非递归版的对比。实测在 n=10⁶ 时，非递归版比递归版快 10% 到 20%，主要省在函数调用和临时数组分配上。但非递归版代码更难写对，所以如果不是性能敏感场景，递归版的清晰度更值得。

6.2 近乎有序的数据上，冒泡的优化版有多能打

构造一个几乎有序的数组（比如随机交换 10 个位置），冒泡的提前退出优化能让它跑出接近 O(n) 的成绩，比归并还快。这是因为归并无论如何都要跑满 log n 层，而冒泡一轮就发现没交换直接退出。这个现象说明：没有绝对好的算法，只有匹配数据特征的算法。面试时如果被问"什么排序最快"，答"看数据"比答具体名字更显功底。

6.3 非递归归并的 width 从 1 开始还是从 2 开始

有人习惯把 width 初始化为 2，先手动合并相邻两个元素，再进入循环。这样能少一轮循环，但代码多了一段特殊处理，得不偿失。从 1 开始，第一轮就是把长度为 1 的段两两合并，逻辑统一，不容易错。性能上那一轮循环的开销可以忽略，没必要为这点优化牺牲可读性。

6.4 用哨兵值简化 merge 的写法及其代价

有些教材在 merge 时给左右段末尾各加一个"哨兵"（比如正无穷），这样就不用判断"某一边是否取完"，循环里只管比较。这个技巧在 C 语言里很常见，因为可以省掉边界判断。但在 Python 里，加哨兵意味着要额外构造带哨兵的数组，反而增加了开销。而且哨兵值的选择有讲究，如果数组里可能出现比哨兵更大的值，逻辑就错了。所以这个技巧了解即可，实际写 Python 时用前面那种"先判空再比较"的写法更稳。

7. 把这三个排序串起来的一张练习清单

光看不动手，过两天就忘。下面这份清单按难度递进，每完成一项就对照前面的章节检查，能覆盖绝大部分易错点。

第一项，手写递归版归并，要求不看任何参考，写完用[38, 27, 43, 3, 9, 82, 10]手动模拟一遍递归树，确认每层的区间和 merge 调用都对得上。第二项，把递归版改成非递归版，重点检查 width 的翻倍时机和 mid、right 的 min 兜底。第三项，给两个版本都加上稳定性测试，用带原始下标的相等元素验证。第四项，手写冒泡的优化版和选择排序，分别测最好情况和最坏情况的比较次数，和表格里的理论值对照。第五项，构造一个近乎有序的数组，比较冒泡优化版和归并的实际耗时，体会"数据特征决定算法选择"。

做完这五项，归并排序的递归与非递归、冒泡和选择的取舍，基本就刻在脑子里了。后面再遇到"手写一个稳定排序"或者"不用递归实现归并"这类问题，直接默写加微调就行。

最后分享一个我自己常用的调试习惯：写完任何排序，先跑三组数据——空数组、单元素数组、已经有序的数组。这三组能筛掉大部分边界错误，尤其是递归版的终止条件和非递归版的 width 循环条件。很多人写完直接上随机大数组，结果报错信息指向一个莫名其妙的下标，回头查半天，其实用空数组一跑就暴露了。这个习惯花不了几秒钟，但省下的调试时间是以小时计的。