外部排序 (External Sort)

Published: Sun Feb 15 2026 | Modified: Wed Feb 18 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