跳轉到

3.1 外部合併排序#

概念說明#

外部合併排序（External Merge Sort）是處理「資料比記憶體大」的標準方法。假設有 N 個分頁的資料要排序，而記憶體只有 B 個分頁的緩衝空間（B ≥ 3）。演算法分兩個階段：

  1. 排序階段（run generation）：每次讀入 B 頁，在記憶體中用任意內部排序法排好，寫回磁碟成為一個「段落（run）」。每個 run 最多 B 頁，共產生 ⌈N/B⌉ 個 run。
  2. 合併階段（merging）：每輪以 B-1 個緩衝頁讀取 B-1 個 run 進行多路合併，剩下 1 頁作為輸出緩衝。每輪合併把 run 數除以 (B-1)，直到只剩 1 個 run。

關鍵洞察：合併是「順序存取」為主的操作。只要合併時各 run 依序讀取，就能享受順序 I/O 的低延遲，甚至被作業系統的預讀機制加速。這是它勝過所有跳躍式存取排序法的根本原因。

演算法步驟#

  1. 讀入前 B 頁 → 內部排序 → 寫出 run₁；重複直到所有資料變成 ⌈N/B⌉ 個有序 run。
  2. 進行合併輪次：每輪挑選至多 B-1 個 run，以最小堆維護各 run 當前記錄，輸出到新 run。
  3. 當 run 數 ≤ 1 時結束。

Python 範例：模擬磁碟上的外部合併排序#

import heapq, random

PAGE = 100          # 每頁 100 筆記錄
MEM_PAGES = 5       # 記憶體可容納 5 頁

def external_merge_sort(records, io={"r": 0, "w": 0}):
    disk = {}  # 模擬磁碟，鍵為 run 編號
    # 階段一：產生初始 run
    runs, nid = [], 0
    for i in range(0, len(records), PAGE * MEM_PAGES):
        chunk = sorted(records[i:i + PAGE * MEM_PAGES])
        runs.append(("run", nid)); nid += 1
        disk[runs[-1]] = chunk
        io["r"] += 1; io["w"] += 1   # 讀入、寫出各算一批（簡化）
    # 階段二：反覆合併
    width = MEM_PAGES  # 每次合併 MEM_PAGES 個 run
    while len(runs) > 1:
        new_runs = []
        for i in range(0, len(runs), width):
            group = runs[i:i + width]
            merged = list(heapq.merge(*(disk[g] for g in group)))
            for g in group: del disk[g]
            new_runs.append(("run", nid)); nid += 1
            disk[new_runs[-1]] = merged
            io["r"] += len(group); io["w"] += 1
        runs = new_runs
    return disk[runs[0]], io

random.seed(7)
data = random.sample(range(10**6), 10000)   # 100 頁、10 萬筆 → 10000 筆示範
result, io = external_merge_sort(data)
print("排序正確:", result == sorted(data))
print("I/O 統計:", io)

複雜度與 I/O 成本分析#

  • CPU 時間：O(N log N)（每筆記錄在每輪合併參與一次堆操作）。
  • I/O 成本：排序階段讀 N 頁寫 N 頁；合併共 log_{B-1}(N/B) 輪，每輪讀 N 寫 N。總計 2N + 2N·log_{B-1}(N/B) 次分頁 I/O。 以 N=1000 頁、B=11 為例：log₁₀(100)≈2，總成本 2×1000 + 2×1000×2 = 6000 次 I/O。
  • 最好的情況（單一 run、一次合併）：2N + 2N。

練習#

  1. 資料 10,000 頁、緩衝 101 頁，計算外部合併排序的總 I/O 次數。
  2. 若緩衝只剩 2 頁（B=2），合併階段會退化成什麼？成本公式變多少？
  3. 修改範例，在排序階段統計精確到「頁」的讀寫次數，驗證 2N 項。