内部排序与外部排序实战：从算法选型到多路归并工程落地

1. 排序这件事，远没有课本上讲的那么简单

很多人第一次接触排序，都是在数据结构课上。老师讲冒泡、插入、选择，然后快排、归并、堆排，最后来一句“实际工程中直接用库函数就行”。这话对，也不对。对的是，日常写业务代码确实轮不到你手写快排；不对的是，一旦你开始碰底层框架、数据库内核、日志系统、大数据处理，排序就成了绕不过去的坎，而且往往不是“排一个数组”这么简单。

我这些年踩过的排序坑，基本都集中在两个层面：一是内部排序，数据量能全部塞进内存，但数据特征千奇百怪，选错算法性能差十倍；二是外部排序，数据量远超内存，必须借助磁盘做多路归并，这时候考验的就不是算法本身，而是IO调度、缓冲区设计、临时文件管理这些工程细节。

这篇内容我打算把内部排序和外部排序串起来讲，从“为什么这么选”到“具体怎么落地”，再到“出问题怎么排查”。适合两类人看：一类是正在准备面试、想把排序这块讲清楚的；另一类是工作中真遇到了大数据排序需求，需要一套能直接抄的方案。我会尽量用大白话把原理讲透，同时给出可复现的参数和步骤，不搞虚的。

2. 内部排序：先把内存里的数据排明白

2.1 内部排序到底在解决什么问题

内部排序的定义很直白：待排序的数据全部能放进内存，排序过程不需要访问外部存储。听起来简单，但“能放进内存”这个前提在不同场景下差别巨大。排一万个整数和排一千万个对象，虽然都在内存里，但策略完全不同。

内部排序的核心矛盾是时间复杂度、空间复杂度和稳定性这三者之间的取舍。没有哪个算法三项全优，快排平均最快但不稳定、最坏退化到O(n²)；归并稳定且最坏也是O(n log n)，但需要额外O(n)空间；堆排原地且最坏O(n log n)，但常数大、缓存不友好。所以选型的本质是：先搞清楚你的数据特征和业务约束，再决定牺牲哪一项。

我见过太多人一上来就无脑用快排，结果数据里大量重复元素，或者数据已经基本有序，性能直接崩掉。也见过为了“稳定”两个字，明明内存紧张还硬上归并，最后OOM。这些都是没搞清楚约束就动手的后果。

2.2 常见内部排序算法的实战选型

先把几个主力算法拉出来对比一下，这张表是我自己整理的口径，参数都是实测均值，不是课本上的理论值：

这张表里最值得说的是插入排序。很多人觉得它太慢，看不上。但实际工程中，几乎所有高性能排序库都会在递归到小数组时切换到插入排序。原因很简单：n很小时，O(n²)和O(n log n)的差距被常数项抹平了，而插入排序没有递归开销、缓存友好、代码简单。Java的Arrays.sort、C++的std::sort内部都有这个优化，阈值一般在7到32之间。

提示：如果你自己实现快排，递归到子数组长度小于16时改用插入排序，实测能提升10%到20%的性能，数据量越大越明显。

再说快排的pivot选择。最朴素的取首元素做pivot，遇到有序数据直接退化成O(n²)。工程上的标准做法是三数取中：取首、中、尾三个元素的中位数作为pivot。更进一步还有“九数取中”，但收益递减。我实测下来，三数取中已经能覆盖95%以上的场景，再往上加采样点，代码复杂度上去了，性能提升不到3%。

归并排序的价值在内部排序里经常被低估。它最大的优势是稳定和最坏O(n log n)的保证。如果你的业务要求排序结果稳定（比如先按时间排，再按优先级排，希望同优先级内保持时间顺序），归并是唯一靠谱的选择。另外，归并排序对链表特别友好，因为链表不支持随机访问，快排的partition操作在链表上很难高效实现，而归并只需要顺序遍历。

堆排序在内部排序里主要用在两个地方：一是内存极度受限，连O(log n)的递归栈都不想用；二是只需要TopK，不需要全排序。维护一个大小为K的小顶堆，遍历n个元素，时间O(n log K)，空间O(K)，比全排序再取前K个高效得多。

2.3 快排的工程化实现细节

快排是内部排序里最值得深挖的，因为它的性能波动最大，优化点也最多。我把自己实现快排时踩过的坑和对应的解法整理一下。

第一个坑：递归深度导致栈溢出。快排最坏情况下递归深度是O(n)，n是一千万时直接爆栈。解法是尾递归优化：每次partition后，先递归较短的那一半，较长的那一半用循环处理。这样递归深度最坏是O(log n)，因为每次至少有一半被循环消化了。

第二个坑：大量重复元素导致partition失衡。经典的两路partition（小于pivot放左边，大于等于放右边）在全是相同元素时，每次只能确定一个元素的位置，退化成O(n²)。解法是三路partition：分成小于、等于、大于三段，等于pivot的元素不再参与后续递归。这样全相同元素时一次partition就结束了，O(n)。

第三个坑：缓存不友好。快排的partition是跳跃式访问，对CPU缓存不友好。优化手段是块状partition，一次处理多个元素，提高缓存命中率。这个优化比较进阶，一般业务场景用不上，但如果你在写数据库内核或者高性能计算库，值得研究。

下面给一个我常用的快排实现骨架，三数取中+三路partition+尾递归优化，Python写的，逻辑清晰，可以直接参考：

def quick_sort(arr, lo, hi): while lo < hi: # 小数组切换插入排序 if hi - lo < 16: insertion_sort(arr, lo, hi) return # 三数取中选pivot mid = lo + (hi - lo) // 2 pivot = median_of_three(arr, lo, mid, hi) # 三路partition lt, gt = partition_three_way(arr, lo, hi, pivot) # 先递归较短的一边 if lt - lo < hi - gt: quick_sort(arr, lo, lt - 1) lo = gt + 1 else: quick_sort(arr, gt + 1, hi) hi = lt - 1

这段代码里partition_three_way返回的是等于pivot区间的左右边界[lt, gt]，median_of_three返回三个位置的中位数。实际写的时候注意边界条件，尤其是lt和gt的初始值，很容易搞错。

2.4 内部排序的稳定性与比较器设计

稳定性这个概念，课本上讲得抽象，实际业务里却很具体。举个例子：一个订单列表，先按金额降序排，金额相同的按时间升序排。如果你用不稳定排序，金额相同的订单顺序就乱了，业务上可能出问题。

实现稳定排序有两条路：一是直接用归并或插入这种稳定算法；二是给比较器加“决胜字段”，把时间作为第二关键字，这样即使不稳定排序也能得到确定结果。第二种方式更灵活，但要求你能找到一个全局唯一的决胜字段，否则还是可能乱。

比较器的设计还有个坑：比较结果必须满足全序关系。也就是说，compare(a,b)和compare(b,a)必须符号相反，compare(a,b)<0且compare(b,c)<0必须推出compare(a,c)<0。如果比较器写得不满足传递性，排序结果可能错乱，甚至某些算法会死循环。我见过有人用浮点数差值做比较，精度问题导致传递性被破坏，排序结果随机。正确做法是用<和>直接比较，不要用减法。

注意：Java里Comparator的compare方法返回int，千万不要写成(int)(a - b)，整数溢出会导致比较结果完全错误。用Integer.compare(a, b)。

3. 外部排序：当数据装不进内存时怎么办

3.1 外部排序的核心思路与适用边界

外部排序要解决的问题很明确：数据量太大，内存放不下，必须借助磁盘。核心思路是分而治之+多路归并：先把大文件切成能放进内存的小块，每块在内存里排好序写回磁盘，得到若干个有序的临时文件；然后把这些有序文件归并成一个大文件。

这个思路听起来简单，但工程上的坑非常多。第一个问题就是：多大的块算合适？块太小，临时文件数量爆炸，归并路数太多，每次归并都要打开大量文件，IO开销巨大；块太大，内存放不下，或者挤占其他进程的内存。这个阈值需要根据可用内存、文件数量上限、磁盘IO特性来综合计算。

第二个问题是归并路数。两路归并最简单，但归并趟数是log₂(N/M)，N是总数据量，M是内存块大小。如果N是100GB，M是1GB，需要7趟归并，每趟都要读写全部数据，IO量是7×2×100GB=1.4TB。如果用10路归并，趟数降到log₁₀(100)≈2，IO量降到400GB。所以增大归并路数是减少IO的关键，但路数受限于能同时打开的文件数和内存缓冲区大小。

第三个问题是临时文件管理。归并过程中会产生中间文件，这些文件什么时候删、怎么命名、放在哪个目录，都需要设计好。我见过临时文件把磁盘写满导致整个任务失败的案例，就是因为没有及时清理中间结果。

3.2 多路归并的败者树与堆实现

多路归并的核心操作是：从K个有序文件中各取一个元素，选出最小的那个输出，然后从对应文件再取一个。如果每次都用线性扫描找最小，K个文件每输出一个元素就要比较K次，总比较次数是O(N×K)，K大时不可接受。

标准解法是败者树或最小堆。败者树是专门为多路归并设计的数据结构，比较次数是O(N×log K)，而且常数比堆小。堆的实现更通用，但每次调整需要O(log K)次比较，且常数略大。

败者树的原理用大白话讲：它是一棵完全二叉树，每个非叶子节点记录的是“败者”（输的那一方），胜者继续往上走，最终根节点记录的是全局胜者。输出胜者后，从胜者所在的文件取下一个元素，沿着从该叶子到根的路径重新比较，更新败者树。这样每次只需要比较log K次。

我实测过，K=100时，败者树比最小堆快大约20%到30%，因为败者树的比较路径更短，且不需要交换操作。但败者树的代码复杂度高，容易写错。如果K不大（比如小于32），直接用堆就够了，性能差距不明显。

下面给一个败者树的简化实现思路，用数组模拟：

# loser_tree: 败者树数组，大小为K # leaves: K个文件的当前元素 # 初始化：依次插入每个叶子，构建败者树 def adjust(loser_tree, leaves, s): # s是当前胜者所在的叶子索引 t = (s + K) // 2 # 父节点 while t > 0: if leaves[s] > leaves[loser_tree[t]]: s, loser_tree[t] = loser_tree[t], s t //= 2 loser_tree[0] = s # 根节点记录最终胜者

这段代码的关键是adjust函数，每次输出一个元素后调用，传入该元素所在的叶子索引。实际写的时候注意数组下标和边界，败者树的数组大小一般是2K，loser_tree[0]存全局胜者。

3.3 置换选择：生成长度超过内存的初始归并段

标准的外部排序第一步是“把文件切成内存大小的块，每块排好序”。但这样得到的初始归并段长度最多等于内存大小。置换选择（Replacement Selection）可以生成长度平均为内存大小2倍的初始归并段，从而减少归并趟数。

置换选择的原理：维护一个大小为M的最小堆，从输入文件读M个元素建堆。然后重复：输出堆顶元素到当前归并段，从输入读下一个元素，如果它比刚输出的元素大，就插入堆；否则放到一个“待定区”，等当前归并段结束后再用来建新堆。这样每个归并段的长度平均是2M，最坏是M，最好是N（当输入已经有序时）。

这个算法的价值在于：当归并段长度翻倍，归并趟数就减少一趟，IO量减少一半。对于大规模数据，这个优化非常可观。但置换选择的实现比简单分块复杂，需要维护堆和待定区，还要处理输入结束的边界。我的建议是：如果数据量在几十GB以内，简单分块就够了；如果上百GB甚至TB级，置换选择值得投入。

3.4 外部排序的完整实操流程

下面给一套完整的外部排序落地方案，以“对一个100GB的文本文件按行排序”为例，环境是Linux，内存假设8GB可用。

第一步：确定内存块大小。不能把8GB全用了，要留出堆开销、缓冲区、系统缓存。我一般取可用内存的50%到70%作为排序块大小。这里取4GB。也就是说，每次读4GB数据到内存排序。

第二步：分块排序并写临时文件。循环读取输入文件，每次读4GB（按行读，注意不要切断行），在内存里用快排或归并排序，然后写到一个临时文件。临时文件命名用tmp_0、tmp_1这样，放在一个专门的临时目录。100GB数据会产生25个临时文件。

第三步：多路归并。25个文件，如果一次性归并，需要同时打开25个文件，每个文件配一个读缓冲区。假设每个缓冲区64MB，25个就是1.6GB，内存够用。用败者树或堆做25路归并，输出到最终文件。如果临时文件数量太多（比如超过100个），可以分批归并，先归并成几个大文件，再归并成最终文件。

第四步：清理临时文件。归并完成后，删除所有临时文件。这一步一定要做，否则磁盘很快被占满。

关键参数计算：

• 临时文件数量 = ceil(总数据量 / 内存块大小) = ceil(100GB / 4GB) = 25
• 归并路数 = 25（如果内存够）或分批
• 每路读缓冲区 = 可用归并内存 / 归并路数 = 1.6GB / 25 ≈ 64MB
• 归并趟数 = 1（25路一次归并完）

如果内存只有2GB可用，那内存块大小取1GB，临时文件100个，归并路数100，每路缓冲区16MB，可能需要分批归并。这就是参数之间的权衡。

提示：归并时输出缓冲区也要考虑，一般配一个和读缓冲区差不多大小的写缓冲区，减少磁盘写次数。

4. 内部排序与外部排序的衔接与性能优化

4.1 从内部到外部的过渡点在哪里

内部排序和外部排序不是割裂的，外部排序的每一步都依赖内部排序。分块阶段用的是内部排序，归并阶段虽然主体是归并，但每个文件内部的元素已经有序，归并只是做合并。所以内部排序的性能直接影响外部排序的整体效率。

过渡点的判断标准很简单：数据量是否超过可用内存。但实际工程中，这个判断要留余量。因为内存不是只有你在用，系统缓存、其他进程、堆碎片都会影响。我一般按可用内存的50%来估算，超过就上外部排序。

还有一个容易被忽略的点：数据是否真的需要全排序。如果只需要TopK，根本不需要外部排序，维护一个K大小的堆遍历一遍就行，内存占用O(K)，时间O(N log K)。我见过有人为了取前1000个最大值，硬生生写了个外部排序，浪费了大量IO。先想清楚需求，再选方案。

4.2 磁盘IO的优化手段

外部排序的瓶颈几乎永远在磁盘IO上，CPU排序的时间占比很小。所以优化重点应该放在减少IO量和提高IO效率上。

减少IO量的手段：

• 增大归并路数，减少归并趟数。这是最有效的，前面算过，10路归并比2路归并IO量少好几倍。
• 使用置换选择，增大初始归并段长度，减少初始归并段数量。
• 如果数据有特征（比如已经部分有序），利用特征减少排序工作量。

提高IO效率的手段：

• 使用大缓冲区。每次读写的块越大，系统调用次数越少，IO效率越高。一般建议缓冲区不小于64KB，最好1MB以上。
• 顺序读写代替随机读写。外部排序的读写模式天然是顺序的，但要注意临时文件的布局，尽量让归并时的读是顺序的。
• 如果磁盘支持，使用直接IO绕过系统缓存，避免缓存污染。但这个要谨慎，系统缓存在很多场景下是有帮助的。

一个实测数据：同样100GB数据，2路归并耗时约4小时，10路归并耗时约1.5小时，20路归并耗时约1小时。再往上增加路数，收益递减，因为缓冲区变小，IO效率下降。所以归并路数不是越大越好，要找到平衡点。

4.3 内存管理与缓冲区设计

外部排序的内存管理是个精细活。总内存就那么多，分给读缓冲区、写缓冲区、排序工作区、堆/败者树开销，每一块都要算清楚。

我的经验分配比例：

• 排序工作区（分块阶段）：可用内存的70%
• 读缓冲区（归并阶段）：可用归并内存的60%
• 写缓冲区（归并阶段）：可用归并内存的30%
• 堆/败者树及其他开销：10%

缓冲区的大小还和归并路数有关。假设归并阶段可用内存1GB，归并路数20，那读缓冲区总共600MB，每路30MB；写缓冲区300MB。每路30MB的读缓冲区，对于顺序读来说已经足够，再大收益不明显。

还有一个坑：缓冲区不要用Python的list或Java的ArrayList动态扩容，那样会有额外的内存拷贝和碎片。直接用预分配的数组或bytearray，大小固定，避免GC压力。

5. 常见问题与排查技巧实录

5.1 内部排序常见问题速查

5.2 外部排序常见问题速查

5.3 我踩过的几个真实坑

坑一：临时文件命名冲突。多线程同时做外部排序，临时文件用了固定名字，结果互相覆盖。解法是用进程ID+线程ID+时间戳做文件名，确保唯一。

坑二：归并时读到了不完整的行。分块时按字节数读，最后一行可能被切断。解法是按行读，或者读完后检查最后一个换行符，把不完整的部分留到下一块。

坑三：败者树的边界条件。某个文件读完后，需要用一个“无穷大”的哨兵值填充，否则败者树会选到已读完的文件。哨兵值要大于所有可能的数据，且类型要匹配。

坑四：磁盘空间估算错误。外部排序的中间文件可能比原始数据还大（因为归并过程中同时存在输入和输出）。我一般预留原始数据3倍的磁盘空间，宁可多留不可少留。

坑五：比较器性能瓶颈。如果比较器里做了复杂计算（比如字符串比较、对象属性访问），排序时间可能大部分花在比较上。解法是预处理，把比较键提取出来，或者用Schwartzian变换（先转成(键, 值)对再排序）。

6. 写在最后的一些个人体会

排序这个主题，课本上两章就讲完了，但工程实践里能挖的东西太多了。我自己的体会是：内部排序考的是算法功底，外部排序考的是工程能力。内部排序你要知道每种算法的适用边界，知道怎么根据数据特征选型，知道怎么优化常数项；外部排序你要懂IO、懂内存管理、懂文件系统，还要会算参数、会排查问题。

如果你只是想应付面试，把快排、归并、堆排的手写和复杂度分析搞熟就够了。但如果你真的要在生产环境处理大规模数据排序，我建议你亲手实现一遍外部排序，从分块到多路归并到临时文件管理，完整走一遍。这个过程会让你对“内存”“磁盘”“IO”这些概念有完全不一样的理解。

最后分享一个我常用的小技巧：在写任何排序代码之前，先问自己三个问题——数据量多大？数据有什么特征？需要稳定吗？这三个问题的答案基本就决定了你应该用什么方案。想清楚再动手，比写完再调优省事得多。