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

1. 排序这件事远没有课本上讲的那么简单很多人第一次接触排序都是在数据结构课上。老师讲冒泡、插入、选择然后快排、归并、堆排最后来一句“实际工程中直接用库函数就行”。这话对也不对。对的是日常写业务代码确实轮不到你手写快排不对的是一旦你开始碰底层框架、数据库内核、日志系统、大数据处理排序就成了绕不过去的坎而且往往不是“排一个数组”这么简单。我这些年踩过的排序坑基本都集中在两个层面一是内部排序数据量能全部塞进内存但数据特征千奇百怪选错算法性能差十倍二是外部排序数据量远超内存必须借助磁盘做多路归并这时候考验的就不是算法本身而是IO调度、缓冲区设计、临时文件管理这些工程细节。这篇内容我打算把内部排序和外部排序串起来讲从“为什么这么选”到“具体怎么落地”再到“出问题怎么排查”。适合两类人看一类是正在准备面试、想把排序这块讲清楚的另一类是工作中真遇到了大数据排序需求需要一套能直接抄的方案。我会尽量用大白话把原理讲透同时给出可复现的参数和步骤不搞虚的。2. 内部排序先把内存里的数据排明白2.1 内部排序到底在解决什么问题内部排序的定义很直白待排序的数据全部能放进内存排序过程不需要访问外部存储。听起来简单但“能放进内存”这个前提在不同场景下差别巨大。排一万个整数和排一千万个对象虽然都在内存里但策略完全不同。内部排序的核心矛盾是时间复杂度、空间复杂度和稳定性这三者之间的取舍。没有哪个算法三项全优快排平均最快但不稳定、最坏退化到O(n²)归并稳定且最坏也是O(n log n)但需要额外O(n)空间堆排原地且最坏O(n log n)但常数大、缓存不友好。所以选型的本质是先搞清楚你的数据特征和业务约束再决定牺牲哪一项。我见过太多人一上来就无脑用快排结果数据里大量重复元素或者数据已经基本有序性能直接崩掉。也见过为了“稳定”两个字明明内存紧张还硬上归并最后OOM。这些都是没搞清楚约束就动手的后果。2.2 常见内部排序算法的实战选型先把几个主力算法拉出来对比一下这张表是我自己整理的口径参数都是实测均值不是课本上的理论值算法平均时间最坏时间空间稳定性适用场景快速排序O(n log n)O(n²)O(log n)不稳定通用首选数据随机分布归并排序O(n log n)O(n log n)O(n)稳定需要稳定、链表排序、外部排序基础堆排序O(n log n)O(n log n)O(1)不稳定内存极紧、只要TopK插入排序O(n²)O(n²)O(1)稳定小数组n32、基本有序计数排序O(nk)O(nk)O(k)稳定整数且范围小基数排序O(d(nk))O(d(nk))O(nk)稳定定长整数/字符串这张表里最值得说的是插入排序。很多人觉得它太慢看不上。但实际工程中几乎所有高性能排序库都会在递归到小数组时切换到插入排序。原因很简单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是100GBM是1GB需要7趟归并每趟都要读写全部数据IO量是7×2×100GB1.4TB。如果用10路归并趟数降到log₁₀(100)≈2IO量降到400GB。所以增大归并路数是减少IO的关键但路数受限于能同时打开的文件数和内存缓冲区大小。第三个问题是临时文件管理。归并过程中会产生中间文件这些文件什么时候删、怎么命名、放在哪个目录都需要设计好。我见过临时文件把磁盘写满导致整个任务失败的案例就是因为没有及时清理中间结果。3.2 多路归并的败者树与堆实现多路归并的核心操作是从K个有序文件中各取一个元素选出最小的那个输出然后从对应文件再取一个。如果每次都用线性扫描找最小K个文件每输出一个元素就要比较K次总比较次数是O(N×K)K大时不可接受。标准解法是败者树或最小堆。败者树是专门为多路归并设计的数据结构比较次数是O(N×log K)而且常数比堆小。堆的实现更通用但每次调整需要O(log K)次比较且常数略大。败者树的原理用大白话讲它是一棵完全二叉树每个非叶子节点记录的是“败者”输的那一方胜者继续往上走最终根节点记录的是全局胜者。输出胜者后从胜者所在的文件取下一个元素沿着从该叶子到根的路径重新比较更新败者树。这样每次只需要比较log K次。我实测过K100时败者树比最小堆快大约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函数每次输出一个元素后调用传入该元素所在的叶子索引。实际写的时候注意数组下标和边界败者树的数组大小一般是2Kloser_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个文件每个文件配一个读缓冲区。假设每个缓冲区64MB25个就是1.6GB内存够用。用败者树或堆做25路归并输出到最终文件。如果临时文件数量太多比如超过100个可以分批归并先归并成几个大文件再归并成最终文件。第四步清理临时文件。归并完成后删除所有临时文件。这一步一定要做否则磁盘很快被占满。关键参数计算临时文件数量 ceil(总数据量 / 内存块大小) ceil(100GB / 4GB) 25归并路数 25如果内存够或分批每路读缓冲区 可用归并内存 / 归并路数 1.6GB / 25 ≈ 64MB归并趟数 125路一次归并完如果内存只有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 内部排序常见问题速查问题现象可能原因排查方法解决方案排序结果不稳定用了不稳定算法检查算法类型换归并或加决胜字段快排性能突然变差数据有序或大量重复打印pivot分布三数取中三路partition排序后结果错乱比较器不满足全序检查比较器传递性用和直接比较小数组排序慢递归开销大统计递归深度小数组切插入排序内存溢出归并空间O(n)检查空间复杂度换堆排或原地归并5.2 外部排序常见问题速查问题现象可能原因排查方法解决方案临时文件占满磁盘未及时清理检查临时目录归并后立即删除归并阶段极慢归并路数太少计算归并趟数增大路数或分批归并打开文件数超限归并路数超过限制查看系统限制分批归并或增大限制内存不足缓冲区分配过多检查内存分配减小缓冲区或路数输出文件顺序错败者树实现错误小数据量验证检查adjust逻辑5.3 我踩过的几个真实坑坑一临时文件命名冲突。多线程同时做外部排序临时文件用了固定名字结果互相覆盖。解法是用进程ID线程ID时间戳做文件名确保唯一。坑二归并时读到了不完整的行。分块时按字节数读最后一行可能被切断。解法是按行读或者读完后检查最后一个换行符把不完整的部分留到下一块。坑三败者树的边界条件。某个文件读完后需要用一个“无穷大”的哨兵值填充否则败者树会选到已读完的文件。哨兵值要大于所有可能的数据且类型要匹配。坑四磁盘空间估算错误。外部排序的中间文件可能比原始数据还大因为归并过程中同时存在输入和输出。我一般预留原始数据3倍的磁盘空间宁可多留不可少留。坑五比较器性能瓶颈。如果比较器里做了复杂计算比如字符串比较、对象属性访问排序时间可能大部分花在比较上。解法是预处理把比较键提取出来或者用Schwartzian变换先转成(键, 值)对再排序。6. 写在最后的一些个人体会排序这个主题课本上两章就讲完了但工程实践里能挖的东西太多了。我自己的体会是内部排序考的是算法功底外部排序考的是工程能力。内部排序你要知道每种算法的适用边界知道怎么根据数据特征选型知道怎么优化常数项外部排序你要懂IO、懂内存管理、懂文件系统还要会算参数、会排查问题。如果你只是想应付面试把快排、归并、堆排的手写和复杂度分析搞熟就够了。但如果你真的要在生产环境处理大规模数据排序我建议你亲手实现一遍外部排序从分块到多路归并到临时文件管理完整走一遍。这个过程会让你对“内存”“磁盘”“IO”这些概念有完全不一样的理解。最后分享一个我常用的小技巧在写任何排序代码之前先问自己三个问题——数据量多大数据有什么特征需要稳定吗这三个问题的答案基本就决定了你应该用什么方案。想清楚再动手比写完再调优省事得多。