电脑用久了，总会遇到一些“卡壳”的情况。比如你打算整理上万张照片，或者处理几百万条销售记录，程序刚跑起来就提示内存不足。这时候你会发现，不是电脑配置不行，而是算法没选对。尤其是涉及到大量数据排序时，传统的快速排序、归并排序根本扛不住，因为它们都依赖内存——可数据太大，根本一次性读不进内存。
什么是外部排序？
简单说，外部排序就是用来处理“内存装不下”的数据的排序方法。它不指望把所有数据一口气加载进来，而是利用磁盘作为中转，分批读取、排序、合并。最常见的场景就是数据库系统在执行 ORDER BY 语句时，面对几GB甚至几十GB的数据，依然能返回有序结果。
和内部排序不同，外部排序的核心矛盾是：磁盘读写慢，但容量大；内存快，但容量小。所以目标不是比谁算法复杂度最低，而是尽量减少磁盘I/O次数。
多路归并排序：最经典的外部排序方法
假设你有一个10GB的日志文件，而你的电脑只有4GB内存。直接排序不可能，但可以这么做：
第一步，把大文件拆成若干个小块，每块大小控制在内存可处理范围内。比如每次读100MB，用快速排序排好，再写回磁盘。这样你会得到100个已排序的小文件。
第二步，进行“多路归并”。同时打开这100个小文件，每个文件读取一部分内容到内存缓冲区，然后从100个缓冲区中选出最小的记录输出到最终结果文件中。一旦某个缓冲区空了，就再从对应文件读取下一批数据。
这个过程就像100个人排队，每人手里有一叠已经排好序的卡片，你每次只看每个人手上最上面那张，挑最小的拿走，谁的被拿走了，谁就翻下一张。
/* 外部排序多路归并伪代码示例 */
divide file into chunks;
for each chunk:
load into memory;
sort using quicksort;
write sorted chunk to disk;
open all sorted chunks;
create output file;
while not all chunks exhausted:
read one record from each non-empty chunk buffer;
find the smallest among them;
write it to output file;
refill buffer if empty;
close all files;优化技巧：败者树与缓冲区管理
如果真有100个归并路数，每次比较都要遍历100个元素找最小值，效率很低。这时可以用“败者树”结构，把比较过程组织成一棵树，每次只需要做 log(100) 次比较就能找到最小值，大大减少CPU开销。
另外，磁盘读写尽量用大块连续I/O，避免频繁小读小写。给每个输入文件分配足够大的读缓冲区，输出也采用缓冲写入，能显著提升性能。
现实中的应用
你在Excel里打开一个百万行的表格，点“按销售额排序”，软件背后很可能就在跑外部排序。大型电商平台每天生成的订单报表，也不是靠堆内存解决的。就连手机相册按时间排序几千张照片，如果处理不当也会卡顿，本质也是小规模的外部存储问题。
理解外部排序方法，不只是为了写算法，更是为了明白：当资源有限时，换一种思路往往比硬拼硬件更有效。下次你发现程序在排序时疯狂读硬盘，别急着换电脑，先看看是不是该换算法了。