题目

对 10TB 的数据文件进行排序，应使用的方法是( )。

错因

A

希尔排序是内部排序——它通过分组比较和交换，要求全部数据装入内存才能按下标分组。10TB 的数据远超任何普通服务器的内存容量（典型机器内存 16GB～512GB，差几个数量级），希尔排序无法跑起来。希尔排序适合"中等规模、需要原地排序"的内部场景，不适合外存数据。

B

堆排序虽然空间复杂度只有 （不算输入数组本身），但同样要求所有元素都在数组里，每一步要随机访问任意位置（堆调整时）。10TB 数据放外存上时，堆调整每一步都引发磁盘随机 I/O，慢到不可用。堆排序的省空间优势只在内存内才成立，对外存数据无能为力。

C

快速排序也是内部排序，且其分区操作要在数组上做随机访问、对子数组递归。如果把 10TB 数据放磁盘，分区时每次比较都引发随机 I/O，性能会比顺序读写的归并排序差几个数量级。即使变种快排（如三路快排）也跳不出"需要随机访问全数组"这个本质限制。

总解析

关键判断：10TB ≫ 内存容量 → 这是外部排序问题，不是内部排序。

外部排序的标准做法 = 多路归并：

1. 生成初始顺串（Run）：把 10TB 文件分块，每次读入 字节（ = 内存大小）到内存，用任意内部排序算法排好后写回磁盘，得到一个有序顺串。重复这一步直到全部数据形成 个顺串。
2. 多路归并：维护一个最小堆（败者树），对若干个顺串做 路归并：每次从堆顶取出最小元素写到输出文件、再从该顺串读下一个元素入堆。归并轮次约 。
3. 重复归并直到只剩一个顺串——这就是排序结果。

为什么只有归并排序能胜任：

关键性质	归并排序	快/堆/希尔
是否需要随机访问全数据	否——只需顺序读 / 顺序写	是
能否分块独立处理	能——分块排序后多路归并	不能
磁盘 I/O 是否友好	顺序 I/O，速度接近读写带宽	随机 I/O，速度慢百倍
已被工业广泛采用	大数据排序、外部排序、MapReduce shuffle 都用它	不用

口诀：

• 数据量 ≤ 内存 → 内部排序（快排 / 堆排 / 希尔等）。
• 数据量 ≫ 内存 → 外部排序 = 归并排序。

10TB 显然远超内存——这种"问哪种排序处理大文件"的题，几乎闭眼选归并排序。

最终答案是 D（归并排序）。