外部排序實戰：海量數據歸並與敗者樹優化全解析

當數據量遠超記憶體容量（如 512MB 甚至 1GB 整數排序），內部排序算法失效，必須轉向外部排序。本文以完整 C 實現為例，深度講解「分治+多路歸並」核心流程、敗者樹優化原理、測試數據生成及跨平台編譯運行指南。

核心思想：分治 + 多路平衡歸並

假設 72KB 文件（18K 整數），磁盤塊 4KB：

1. 初始運行生成：讀入 4KB 塊 → 內部快排 → 輸出 18 個有序歸並段 (R1~R18)。
2. 多輪 K 路歸並：每輪將 K 個段合併為 1 段，段數呈指數級下降。示例採 4 路：
   • 第 1 輪：18 段 → 5 段 (R11~R15) → 寫入 5 臨時文件。
   • 第 2 輪：5 段 → 2 段 (R21, R22) → 寫入 2 文件。
   • 第 3 輪：2 段 → 1 段 (R31) → 最終有序文件。

磁盤 I/O 次數 ∝ log_K(M)，增大 K 可減少輪數，但會增加單輪合併複雜度。

敗者樹：將 K 路合併從 O(K) 降至 O(log K)

傳統 K 路合併需比較 K-1 次選出最小值，總複雜度 O(N·K)。敗者樹（Loser Tree）是完全二叉樹結構，葉節點存 K 路當前元素，非葉節點存「較大者」索引，根節點即全局最小值索引。調整複雜度 O(log K)，總複雜度降為 O(N·log K)，對海量數據極具價值。

構建流程：自底向上比較，敗者上移，勝者繼續向上 PK。調整時僅需從葉節點向根路徑比較 log K 次。

工程實現亮點（節選關鍵結構）

typedef struct run_t {
    int *buf;       // 輸入緩衝區
    int length;     // 緩衝區有效元素數
    int offset;     // 文件讀取位置
    int idx;        // 緩衝區讀指針
} run_t;

static int ls[MAX_WAYS];  // 敗者樹數組，ls[0] 存最小元素所在路索引

• 雙緩衝區：輸入 `run_t.buf` 輪流讀取磁盤塊；輸出 `buffer` 積滿 128KB 寫入磁盤，減少系統調用。
• 文件雙前綴切換：`foo_`/`bar_` 交替作為輸入/輸出前綴，避免同名覆蓋。
• 哨兵值 MAX_INT：路耗盡時填入 `~(1<<31)`，自動退出合併。

測試數據生成與性能實測

# 生成 512MB 隨機二進制文件 (128M 整數)
dd if=/dev/urandom of=random.dat bs=1M count=512

編譯運行：

gcc sort.c -o sort -g
./sort random.dat 64  # 64 路歸並

實測數據 (i5/4GB RAM)：

近線性擴展，驗證敗者樹 + 多路歸並高效性。

驗證腳本：讀取二進制文件檢查有序性

附贈簡易查看程序，每行打印 10 個整數，便於人工抽查或管道對比 `sort -c`。

避坑指南

• 確保 `PAGE_SIZE` (4096) 與磁盤塊大小一致，否則 I/O 放大。
• `BUF_PAGES=32` → 128KB 緩衝區，平衡記憶體與系統調用開銷。
• 32 位系統注意 `long` 與指針大小差異，代碼中 `get_time_usecs` 使用 `struct timeval` 保證微秒級計時。

外部排序是大數據處理基石，掌握其工程化實現，讓你從容應對「內存裝不下」的排序挑戰。