外部排序是指对存储在外存（如硬盘）中的大规模数据进行排序的过程，由于数据量远超内存容量，无法一次性全部加载到内存中处理，因此需要结合内存中的内部排序与外存数据的分段读写、归并操作来完成整体排序。其核心思想是“分治”：先将大数据分割成可载入内存的小块，用内部排序生成有序段，再通过多路归并逐步合并为全局有序文件。
归并排序是外部排序的核心方法，分为两个阶段：
生成初始归并段（Run Generation）：
将大文件划分为若干块，每块读入内存，使用高效的内部排序算法（如快速排序、堆排序）排序后写回外存，形成多个有序的初始归并段。多路归并（Merge Phase）：
将多个有序归并段逐步合并为更大的有序段，直至整个文件有序。为了提高效率，通常采用k 路平衡归并，即每次从 k 个归并段中各取一个记录进行比较，选出最小者输出，并从对应段中读取下一个记录继续比较。
以“8 个初始归并段”为例，若采用 4 路平衡归并，则第一轮合并两次（4+4），得到 2 个大段；第二轮将这两个大段再合并一次，共需 3 轮 I/O 操作即可完成排序，显著减少了磁盘访问次数。
在实现 k 路归并时，关键是如何高效地从 k 个输入流中选择当前最小关键字。为此引入了树形选择排序的结构优化：
胜者树（Winner Tree）：构建一棵完全二叉树，叶子节点代表 k 个归并段当前待比较的记录，内部节点记录“胜者”（较小值）。每次比较沿路径向上进行，根节点即为当前最小元素。输出后只需更新对应叶子节点并重新调整其父路径上的比较结果，即可快速获得下一个最小值。
败者树（Loser Tree）：与胜者树类似，但每个非叶节点保存的是比较中的“失败者”，优点在于重构路径更稳定、逻辑更清晰，常用于实际外部排序实现中，提升多路归并效率。
外部排序的主要特点包括：
- 适用于数据规模远大于可用内存的场景；
- 性能瓶颈在于磁盘 I/O 次数，因此目标是最小化内外存之间的数据交换；
- 多路归并结合胜者树或败者树能有效减少归并轮数和每轮的读写开销，是提高效率的关键技术。
# 简化的外部排序框架示例（不包含具体磁盘操作）importheapqdefexternal_sort(file_path,block_size):# 阶段1：生成归并段runs=[]withopen(file_path,'r')asf:whileTrue:block=[int(x)forxinf.readline().strip()]iff.readable()else[]ifnotblock:breakblock.sort()# 内部排序run_file=f"run_{len(runs)}.txt"withopen(run_file,'w')asrf:rf.write(' '.join(map(str,block)))runs.append(run_file)# 阶段2：k路归并（使用最小堆模拟败者树/优先队列）withopen("sorted_output.txt","w")asoutput:file_iterators=[open(run,'r')forruninruns]heap=[]# 初始化堆fori,itinenumerate(file_iterators):val=it.readline()ifval:heapq.heappush(heap,(int(val.strip()),i))whileheap:min_val,src_idx=heapq.heappop(heap)output.write(f"{min_val}\n")next_val=file_iterators[src_idx].readline()ifnext_val:heapq.heappush(heap,(int(next_val.strip()),src_idx))foritinfile_iterators:it.close()k路平衡归并的归并轮数可以通过对初始归并段的数量 $ n $ 和每次合并的路数 $ k $ 进行数学分析得出。
在k路平衡归并中，每一轮将最多 $ k $ 个有序归并段合并为 1 个新的有序段，因此每轮后归并段数量从 $ m $ 减少为 $ \lceil m / k \rceil $。重复此过程，直到只剩 1 个最终有序段。
✅ 计算公式：
设初始有 $ n $ 个归并段，采用 $ k $ 路平衡归并，则所需归并轮数 $ R $ 为满足以下条件的最小整数：
R=⌈logkn⌉ R = \left\lceil \log_k n \right\rceilR=⌈logkn⌉
更精确地说，是不断执行 $ n = \lceil n/k \rceil $ 直到 $ n = 1 $ 的迭代次数。
🔍 示例说明：
例1：$ n = 8 $ 个初始归并段，使用 $ k = 2 $ 路归并（二路归并）
- 第1轮：8 → 4
- 第2轮：4 → 2
- 第3轮：2 → 1
→ 共需3 轮
而 $ \lceil \log_2 8 \rceil = \lceil 3 \rceil = 3 $，符合。
例2：$ n = 16 $, $ k = 4 $
- 第1轮：16 → 4
- 第2轮：4 → 1
→ 共需2 轮
$ \lceil \log_4 16 \rceil = \lceil 2 \rceil = 2 $，正确。
例3：$ n = 10 $, $ k = 3 $
- 第1轮：10 → ⌈10/3⌉ = 4
- 第2轮：4 → ⌈4/3⌉ = 2
- 第3轮：2 → ⌈2/3⌉ = 1
→ 共需3 轮
而 $ \lceil \log_3 10 \rceil = \lceil 2.095 \rceil = 3 $，也成立。
📌 注意事项：
- 实际中要求归并过程“平衡”，即尽可能每个归并段都参与每轮合并，避免某些段提前结束；
- 若 $ n $ 不是 $ k $ 的幂次，最后一轮可能不足 $ k $ 个段参与，但仍计入一轮；
- 使用败者树或胜者树可高效实现每轮中的多路选择操作，降低比较开销。
✅ 总结：
归并轮数 $ R $ 的计算方法为：
R=⌈logkn⌉ R = \left\lceil \log_k n \right\rceilR=⌈logkn⌉
等价于反复执行 $ n = \lceil n / k \rceil $ 的次数，直到结果为 1。
这直接影响外部排序的 I/O 次数，因此增大 $ k $ 可显著减少轮数和磁盘访问，但需更多内存缓冲区支持。
