外部排序 (External Sort)

Published: Sun Feb 15 2026 | Modified: Sat Feb 07 2026 , 2 minutes reading.

外部排序：内存建筑师

算法背后的故事：只有小课桌的图书馆员

想象你是一位负责整理 100 万本书的图书馆员。然而，你的办公室非常局促——你的书桌一次只能放下 10 本书。剩下的书都存放在马路对面那个巨大但搬运缓慢的仓库里。

你该如何给它们排序？

你无法一次把 100 万本书都搬到桌子上。所以，你先搬来 10 本，排好序，然后将这叠“已排序的小堆”放回仓库。你不断重复这个过程，直到仓库里有了 10 万个已排序的小堆。

接着，你从每个小堆中各取 第一本书（或者取书桌能容纳的数量），开始一场“大归并”。你比较这些堆顶的书，挑出最小的，逐步构建出最终的总清单。

这就是 外部排序 (External Sorting) 的逻辑。它在计算机发展的早期（20 世纪 50 年代）被发明出来，那时内存 (RAM) 的单位是 KB，而存储在磁带上的数据单位则是 MB。

为什么需要它？

外部排序是 数据工程 领域沉默的巨人。

数据库： 当你在一个 500GB 的表上运行 SELECT ... ORDER BY 时，数据库后台运行的就是外部排序。
日志分析： 对 1TB 的服务器日志进行排序，找出一年中最繁忙的小时。
搜索引擎： 构建海量的倒排索引时，需要排序的数据量远超任何单机的内存上限。

算法是如何“思考”的

这个算法像是一个物流经理，分为两个清晰的阶段工作：

阶段 1：分批排序 (Run Generation)：
- 它读取一段内存放得下的数据块。
- 使用快速的内部排序算法（如快速排序）对其排序。
- 将这个有序块（称为一个 “Run”）写回磁盘。
- 重复此操作，直到所有数据都在磁盘上变成了多个有序块。
阶段 2：多路归并 (K-Way Merge)：
- 它同时打开所有这些磁盘上的有序块。
- 使用 最小堆 盯着每个块的第一个元素。
- 挑出最小的那个，写入最终的输出文件，然后从刚才那个块中读取下一个元素。
- 它就像一条汇聚了多条车道进入单一隧道的超级高速公路。

工程决策：I/O 瓶颈

在外部排序中，CPU 的速度并不重要。磁盘 I/O 就是一切。

顺序 vs 随机： 该算法被设计为大块地顺序读写，因为磁盘的随机寻道速度比顺序读写慢 1000 倍。
并行化： 现代外部排序（如 Spark 或 Hadoop 中的实现）会利用多个磁盘和多台机器并行排序分块，然后通过网络进行归并。

实现参考 (Python 素描版)

import heapq

def external_sort(massive_file, chunk_size):
    # 阶段 1：生成有序的分块 (Runs)
    run_files = []
    with open(massive_file, 'r') as f:
        while True:
            chunk = read_chunk(f, chunk_size) # 读取内存可容纳的大小
            if not chunk: break
            
            chunk.sort() # 内存排序
            run_file = write_to_temp_file(chunk) # 写入临时文件
            run_files.append(run_file)

    # 阶段 2：多路归并
    # 打开所有临时有序块
    handles = [open(rf, 'r') for rf in run_files]
    min_heap = []

    # 1. 将每个块的第一项放入堆中
    for i, h in enumerate(handles):
        line = h.readline()
        if line:
            heapq.heappush(min_heap, (line, i))

    # 2. 归并直到堆为空
    with open('sorted_output.txt', 'w') as out:
        while min_heap:
            smallest, run_idx = heapq.heappop(min_heap)
            out.write(smallest)
            
            # 从刚才贡献了最小值的那个块中读取下一行
            next_line = handles[run_idx].readline()
            if next_line:
                heapq.heappush(min_heap, (next_line, run_idx))

    # 清理
    for h in handles: h.close()

小结

外部排序教会我们：资源限制只是工程上的挑战。通过将庞大的问题拆解为批次，并利用归并的力量，我们可以处理比我们的“思考空间”大无限倍的数据集。它提醒我们，在大数据世界里，最好的建筑师是那些知道如何在仓库与课桌之间高效搬運的人。

Luke Sun