在算法练习平台（PTA）上刷到《寻找大富翁》这道题时，大部分人的第一反应是：排个序，取前M名，完事。如果题目又明摆着要求用归并排序实现，这就不是“完事”那么简单了。题目本身并不复杂，真正考的是对分治排序的理解，以及对数组边界、临时空间、多组输入、输出格式这些底层细节的处理。这篇文章就围绕这道题，把归并排序的完整实现、判题时常见的坑，以及“求前K大”在不同数据规模下的方案取舍一次讲清楚。适合正在学数据结构、准备机试，或者想手写排序练基本功的人阅读。
我自认C语言和排序都还算熟，但第一次提交这道题还是吃了个超时。原因不是归并排序不会写，而是merge函数里每次递归都malloc了一块临时数组，数据量一上来，内存申请和释放的开销直接拖垮了性能。后来把临时数组放到全局、改成自底向上的迭代归并，才真正摸清归并排序的脾气。下面从题目本身开始拆。
1. 题目拆解：考点不在排序结果，而在排序过程
1.1 题面看似简单，实际限制不少
《寻找大富翁》的输入格式一般是这样的：第一行两个正整数 n 和 m，表示有 n 个人、要输出前 m 名；第二行有 n 个正整数，表示每个人的财产。多组测试数据，n 为 0 时结束。输出要求按降序输出前 m 名的财产，数字之间用空格分隔。
这个题面放在日常开发里，一个 sort 就能解决。但在数据结构与算法的配套练习里，题目名称后面往往挂着“归并排序”，这就是很明确的提示：排序函数不能调库，得自己实现。有的版本 n 能到 1000000，m 可能只有 10，也可能接近 n，输入规模一大，很多看起来“能过”的写法就会原形毕露。更关键的是，判题系统不只看最终排序结果对不对，数组越界、多组输入处理不当、输出多一个空格，都会导致提交失败。换句话说，这道题既考算法实现，也考工程细节，两个层面都得稳。
1.2 可选解题路线不止一条
题目没有限制解法时，常见思路有这么几种：
- 暴力选择：每次在剩余元素中找最大值，做 m 轮，时间复杂度 O(nm)，m 稍大就挂。
- 内置排序：调用 C 标准库的 qsort 或者 C++ 的 sort，O(nlogn)，代码量小，但不是这题想考的东西。
- 手写快速排序：平均 O(nlogn)，但最坏可能退化到 O(n^2)，而且不稳定。
- 手写归并排序：稳定 O(nlogn)，额外 O(n) 空间，正是这题的训练目标。
- 小根堆维护前 m 大：O(nlogm)，适合 m 很小的场景。
- 快速选择：用 partition 思路求第 K 大，平均 O(n)，但输出有序前 m 个还需要额外处理。
这些方法各有适用场景。比如 m 固定为 10 时，小根堆复杂度远低于任何全排序；如果只求中位数，快速选择更合适。但题目既然点名归并，那就踏踏实实把归并写熟，顺带再思考一下不同方案的取舍，这比单纯 AC 一道题更有价值。
1.3 归并排序在这个场景里的独特价值
归并排序最大的特点是所有情况下复杂度都是 O(nlogn)，不依赖输入数据的初始顺序。快速排序如果枢轴选得不好，在接近有序的数据上可能退化到 O(n^2)；堆排序虽然也是 O(nlogn)，但不稳定，也不方便扩展成外部排序。归并排序的“分治—合并”结构，是后续学习多路归并、文件外部排序、分布式排序的地基，所以很多课程拿这种题来检验学生是不是真会写分治。
另外，归并排序可以很方便地控制升序还是降序，只需要改一行比较符号。在《寻找大富翁》这种“从大到小输出前 m 个”的题目里，这个特性非常顺手。理解了这一点，后面的代码就是水到渠成的事。
2. 归并排序核心实现：从递归拆分到有序合并
2.1 核心思想：分而治之
归并排序可以类比成整理两叠已经按大小排好的扑克牌：你只需要每次比较两叠牌最上面的一张，把更小的那张抽出来放进新牌堆，直到两叠牌都被抽完，最后得到的新牌堆依然有序。在数组上，分治的第一步是“分”：找到中点，把区间 [left, right] 拆成 [left, mid] 和 [mid+1, right] 两个子区间；第二步是“治”：递归地把两个子区间分别排好；第三步是“合”：调用 merge 函数，把两个有序子区间合并成一个更大的有序区间。
递归入口是对整个数组调用一次 mergeSort，出口是区间只有一个元素时直接返回，因为单个元素天然有序。这个结构理解起来不难，但写代码时会遇到不少细节，尤其是临时数组、边界条件、最后拷贝这三件事，任何一个出问题，排序结果都会错。
2.2 merge 函数逐行讲解
merge 负责把两个相邻有序区间合并。闭区间写法下，左侧区间是 [left, mid]，右侧区间是 [mid+1, right]。三个下标 i、j、k 分别指向左区间、右区间和临时数组的当前位置。
int tmp[MAXN]; void merge(int arr[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] >= arr[j]) // 降序，等号保证稳定 tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= mid) tmp[k++] = arr[i++]; while (j <= right) tmp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = tmp[i]; }第一个 while 是核心，每次从两个有序子区间中挑一个更大的元素放进临时数组。这里的 >= 不是 >，是为了数值相等时优先取左区间元素，保持稳定性。第二个 while 处理左区间剩余，第三个 while 处理右区间剩余。最后必须把临时数组内容拷贝回原数组，否则原数组始终没有被更新，外层递归拿到的还是旧数据。很多人第一次写 merge 时会漏掉最后这个 for 循环，结果排序输出乱序，这个看似不起眼的回写，是整个排序真正“落笔”的地方。
2.3 降序排序与稳定性的一行之差
标准教材里 merge 用的是if (arr[i] <= arr[j])，那是升序。本题要求降序输出，有两种做法：第一种是升序排序后倒着读；第二种是直接把比较符号改成 >=，让归并结果本身就是降序。我推荐第二种，因为归并结束后最大的数就在 a[0]，前 m 个直接顺序输出即可，少一层出错的可能。所有基于比较的排序，降序和升序只差一个比较符号，不需要改算法框架。
稳定性这个问题，很多人在纯数值题里觉得无所谓。“大富翁”只输出财产数字，相同时谁前谁后确实不影响结果。但稳定排序在实际场景中很有用，比如先按工资降序，再按入职时间排序时，稳定排序能保留前一次的相对顺序。养成写 >= 而不是 > 的习惯，表面上是多写一个等号，实际是在建立稳定性的概念。
2.4 边界条件和常见 Bug
- 递归出口：
if (left >= right) return;忘记写，会无限递归。 - 中点计算：
mid = left + (right - left) / 2;比(left + right) / 2更安全，不会在 left+right 很大时整数溢出。 - 区间划分：递归调用是
mergeSort(arr, left, mid)和mergeSort(arr, mid+1, right)，左右都是闭区间，不重叠不遗漏。如果把右边写成 mid，mid 那个元素会被排序两次，右半永久少一个元素。 - 临时数组下标：merge 里 k 从 left 开始，不是从 0 开始。因为 merge 只负责 [left, right] 这一段，k 从 0 开始，回写时就会错位。
- 回写范围：必须
for (i = left; i <= right; i++)回写，写错区间会导致部分数据没排上。
这些错误在大数据量下很难用肉眼发现，必须靠边界分析和少量数据的手动推演。我的建议是先用 n=5 到 10 的小数组，把每次递归拆分的 mid 标出来，配合代码走一遍。调试时可以在 merge 入口打印 left、mid、right，但提交前一定要删掉，否则打印输出会影响判题结果。这种方式比盯着大数据空想要高效得多。
3. 实战：一份可以直接提交的 AC 代码
3.1 递归版完整代码
下面这份代码是 C 语言。全局数组开 100 万不会爆栈，递归深度也只有几十层，完全安全。输入部分兼容多组数据，n 和 m 都为 0 时结束。
#include <stdio.h> #define MAXN 1000005 int a[MAXN]; int tmp[MAXN]; void merge(int arr[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] >= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= mid) tmp[k++] = arr[i++]; while (j <= right) tmp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = tmp[i]; } void mergeSort(int arr[], int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } int main(void) { int n, m; while (scanf("%d %d", &n, &m) == 2) { if (n == 0 && m == 0) break; for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (m > n) m = n; mergeSort(a, 0, n - 1); for (int i = 0; i < m; i++) { if (i > 0) putchar(' '); printf("%d", a[i]); } putchar('\n'); } return 0; }数组 a 和 tmp 都放在全局区，避免函数内定义大数组导致栈溢出；mergeSort 入参是闭区间；排序完成后 a[0] 到 a[m-1] 就是最大的 m 个，直接输出。m > n 时先修正 m，防止输出阶段数组越界。
3.2 多组输入和结束条件的处理
原题很可能采用“多组测试数据，n 为 0 结束”的格式。上面代码里，scanf的返回值作为循环条件，能处理读到文件末尾的情况；又用n == 0 && m == 0作为业务结束条件，能处理题目指定的 0 结束。两种约定都能兼容，是比较稳妥的写法。
如果题目说 m 为 0 时也结束，循环里就不输出数字，直接输出一个空行。有些判题系统对多余空行很敏感，所以这种边界场景需要细读题目。总体思路是：判循环条件看 scanf 返回值，判结束条件看具体数值，不要想当然只判断 n。
3.3 m 大于 n 的防御处理
输入数据可能存在 n=5、m=10 这类不严谨的情况。没有if (m > n) m = n;时，输出阶段会读取 a[5] 到 a[9]，这些位置可能是未初始化的数据，也可能越界到数组末尾之外。全局数组越界读大概率不会立刻崩溃，但输出的数字毫无意义，判题结果自然是答案错误。加一行防御，是写这类题的基本习惯，尤其在 n 上限比较大的题目里。
3.4 迭代版归并：去掉递归调用的优化写法
递归版代码清晰，但函数调用有额外开销。数据量到 100 万时，递归函数调用次数大约是 2n-1 次，也就是 200 万次，这个开销在 C 语言里通常可接受。不过我更喜欢迭代版，因为它省去了递归栈，边界也更统一。
void mergeSortIter(int arr[], int n) { for (int len = 1; len < n; len <<= 1) { for (int i = 0; i + len < n; i += (len << 1)) { int left = i; int mid = i + len - 1; int right = i + (len << 1) - 1; if (right >= n) right = n - 1; merge(arr, left, mid, right); } } }len 表示当前左右两个子区间中左半的长度，初始为 1，代表把两个长度为 1 的有序区间合并成两个元素的有序区间。内层循环的条件i + len < n保证右侧区间存在，否则不合并。每轮结束 len 翻倍，最终整个数组有序。这个版本和递归版共用同一个 merge 函数，复杂度相同，常数略小。在《寻找大富翁》这类明确要求归并的题目里，用迭代版同样能得分，而且踩递归边界的坑更少。
4. 常见问题与排查技巧实录
4.1 一运行就段错误
段错误最常出现在三个位置：数组开太小、局部大数组导致栈溢出、merge 里访问了不存在的下标。
数组开太小很好理解，n 最大 1000000，你只开了 100000，读入时就会越界写。局部大数组的问题我也踩过：把临时数组int tmp[1000005]定义在 main 或 merge 函数里，程序一跑就崩。原因是函数内局部变量放在栈上，进程默认栈空间通常只有几 MB，100 万个 int 就是 4MB，再加上递归调用的多个栈帧，栈很快爆掉。解决办法就是全部放全局区，静态区空间足够大，也不占栈。
如果排除了以上两种，仍然段错误，就检查递归边界。比如mergeSort(arr, left, mid)和mergeSort(arr, mid, right)区间重叠，会导致无限递归，最终栈溢出。这类问题在小数据下可能表现为“还能跑但结果不对”，数据一大就直接崩。
4.2 答案错误，但排序看起来没问题
输出方向错了，是《寻找大富翁》里最容易出现的 WA。题目要求降序输出前 m 个，如果你写的是升序归并，却仍然从 a[0] 开始输出，那输出的就是最小的 m 个，必错。升序归并时，正确做法是从 a[n-1] 往回到 a[n-m]，也就是倒序输出末尾 m 个。相比之下，直接降序归并更直观，输出阶段不会犹豫。
输出格式也容易错。最后一个数字后面不能带多余空格。很多判题系统对多空格并不宽容，所以写稳一点：第一个数字前不输出空格，之后每个数字前输出一个空格。代码里的if (i > 0) putchar(' ')就是干这件事。换行也不要忘，每组输出后都得补一个换行。
4.3 提交超时，先检查这三个地方
第一，merge 里不要创建临时数组。我见过不少写法在 merge 内部用 malloc 申请临时数组，排序完再 free。表面看没问题，但 n=100 万时递归调用会产生大量 malloc/free，系统调用开销非常大，时间直接爆掉。把临时数组定义为全局变量，所有 merge 共用同一块空间，是最基础的优化。
第二，检查有没有死循环。递归边界错误、mid 计算错误、循环变量没有递增，都可能导致程序陷入无限循环。小数据看不出性能问题，提交后就表现为 Time Limit Exceeded。用 n=4 或 n=5 的小数据跑一遍，每一步打印 left、mid、right，很快就能定位。
第三，考虑输入输出效率。scanf 和 printf 在 100 万级别通常够用，但有些评测机配置低，或者数据到了千万级别，就需要手写快读。下面是一个只处理正整数的 readInt 函数，在本题场景够用：
int readInt(void) { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x; }如果要用快读，建议只读普通数据，n 和 m 继续用 scanf 判断结束条件，避免在 EOF 时快读函数陷入死等。不要盲目上快读，1e6 以内的数据用 scanf 已经能通过绝大多数题目。
4.4 从全排序到只找前 K 大的优化思路
如果 m 很小，比如 m=3，只需要前三大，那全排序确实有点浪费。可以维护一个大小为 3 的小根堆，堆顶始终是堆中最小的那个。扫描数组时，只要当前数比堆顶大，就把堆顶替换成当前数，再调整堆。这样每个数最多和堆顶比较一次，复杂度从 O(nlogn) 降到 O(nlog3)，几乎是线性。
但题目明确要求归并时，不能拿这个思路交差。理解归并仍然是主线。学习时把堆排序版也写一遍，对“为什么不同排序适用不同场景”的体会会更深。说到底，算法题的价值不在于找一条最快路径蒙混过关，而在于看清不同工具之间的边界。
4.5 模块化测试：用随机数据验证排序结果
一个很管用的排查方法：单独写一个小程序，生成随机数组，调用你写的 mergeSort，再对照标准库排序结果，验证排序是否正确。如果发现某几组数据不一致，就把数据量调到很小，逐行打印递归过程。调排序的 bug，靠眼睛看大数据输出几乎不可能，但缩小规模后清楚多了。
例如输入 5 个数：5 3 8 1 9，要求降序排序。手推一遍递归：mid=2，左区间 [5,3,8] 排序后是 [8,5,3]，右区间 [1,9] 排序后是 [9,1]，合并时先比较 8 和 9，9 在前，然后 8、5、3、1，最终结果是 [9,8,5,3,1]。如果代码输出和这个不一致，哪一步错了基本一眼可见。
5. 复杂度验证与方案取舍：为什么这道题选归并
5.1 时间复杂度的直观推算
设总数据量为 n，归并排序每一层都要把整个数组扫描一遍，合并总代价是 O(n)。递归过程把数组分成了 logn 层，所以总复杂度是 O(nlogn)。说直白一点，n=1000000 时，log2(n) 大约是 20，每一层都要对 100 万个元素进行读、比、写，总操作在几千万次量级。C 语言完成这个量级通常在一秒上下，前提是临时数组复用、没有频繁内存申请。
空间方面，归并排序需要一个与原数组等长的临时数组，也就是 O(n)。加上递归栈的 O(logn)，整体空间复杂度 O(n)。对 100 万数据来说，两个 int 数组大约 8MB，满足绝大多数题目的内存限制。如果题目内存紧到只有 8MB，n 又到 100 万，int 数组本身就要 8MB，怎么都不够，那就得考虑分块处理了，这正好引出外部排序。
5.2 归并排序、快速排序、堆排序怎么选
学习场景和真实场景要分开看。从学习场景看，题目要求归并，就是要掌握分治思想和稳定排序的实现。从真实场景看，三种排序各有适用面：归并稳定、复杂度可预测，适合数据量大、要求稳定或需要外部排序的场合；快速排序常数小、额外空间少，是绝大多数内存内排序的首选；堆排序空间 O(1)，总能保持 O(nlogn)，但常数较大且不稳定。
| 排序算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 | 典型场景 |
|---|---|---|---|---|---|
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | 大数据、外部排序、链表排序 |
| 快速排序 | O(nlogn) | O(n^2) | O(logn) | 不稳定 | 内存内排序，工程常用 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 需要原地排序且不要求稳定 |
快速排序的最坏情况可以通过随机选枢轴缓解，但工程上引入随机化也要额外代码；归并排序没有这个烦恼，它把“最坏情况”也锁死在 O(nlogn)。这也是为什么排序讲解和某些稳定性敏感的排序场景里，归并依然有一席之地。
5.3 从归并到多路归并：这道题能延伸的方向
如果哪天你面对的不是 100 万个能装进内存的数，而是内存装不下的上亿个数，递归归并就不能直接用了。标准做法是把大文件切块，每块读进内存排序后写回磁盘，形成多个有序小文件，再用堆做多路归并，不断从每个文件头部取最大或最小元素输出。这个过程本质上就是归并排序“合并有序序列”那一步的放大版。
理解了这一点，就会明白为什么课程会在排序题里特意点名归并排序。《寻找大富翁》表面是排序题，背后是在训练一种思路：把大问题切成小块，分别解决，再合并结果。这种思路在分治算法、外部排序、并行计算里反复出现，一次写明白了，后面再遇到类似场景会轻松很多。
我最初写这道题时，第一个版本在 merge 函数里定义了局部临时数组，n=10 万时程序直接崩掉。改成全局数组后，又发现输出的是最小的 m 个数，因为排序方向写成了升序。来回调试之后，我把递归树亲手在纸上画了一遍，才真正理解闭区间和边界条件的含义。如果你现在也在跟这道题较劲，建议先用小数据把 merge 的边界弄透，再谈性能和优化。归并排序写顺之后，再看分治类的题目，心里会踏实很多。
