外部排序實戰：多路歸並 + 敗者樹優化 + 完整 C 代碼詳解

一、外部排序核心流程：分治 + 歸並

當數據量遠超內存（如 1G 文件，內存 128M），外部排序採用「分階段內部排序 → 多輪多路歸並」策略：

1. 分割：將大文件按磁盤塊大小（如 4KB）切分，每塊讀入內存快速排序（快排/歸並排），產生有序初始歸並段（Run）。
2. 多路平衡歸並：每輪從 K 個歸並段中選最小記錄寫入輸出緩衝區，輸出滿則刷盤。每輪歸並段數減少 K 倍，直到剩 1 個段，即最終有序文件。

二、敗者樹優化 K 路選最小

朴素 K 路歸並每次比較 K-1 次，總複雜度 O(N·K)。敗者樹（完全二叉樹，葉子為 K 路當前記錄，內節點記錄「失者」索引）可在 O(log K) 取得最小值，總複雜度降為 O(N log K)，對海量數據極其關鍵。

三、測試數據生成

# 生成 512MB 隨機二進制文件（128M 個 int32）
dd if=/dev/urandom of=random.dat bs=1M count=512

四、核心代碼架構解析

關鍵數據結構

typedef struct run_t {
    int *buf;        // 輸入緩衝區
    int length;      // 緩衝區當前有效記錄數
    int offset;      // 已讀文件偏移
    int idx;         // 緩衝區讀指針
} run_t;

static int ls[MAX_WAYS];  // 敗者樹數組，ls[0] 存最終勝者索引

主流程 main()

1. 解析參數：./sort random.dat 64 → 64 路歸並。
2. 初始化：頁大小 4KB，緩衝 32 頁 (128KB)，分配 K 個 run_t。
3. 首輪：直接讀原文件，快排，寫入 foo_*.dat。
4. 後續輪：從上輪輸出文件讀入，K 路歸並寫 bar_*.dat，雙前綴交替避免文件名衝突。
5. 循環直到 num_runs == 1，輸出耗時統計。

K 路歸並核心 k_merge()

void k_merge(run_t** runs, char* input_prefix, int num_runs, int base, int n_merge) {
    create_loser_tree(runs, num_runs);  // 建樹
    while (live_runs > 0) {
        mr = runs[ls[0]];               // 取勝者
        buffer[bp++] = mr->buf[mr->idx++];
        if (output_buffer_full) flush_to_disk();
        if (mr_buffer_exhausted) {
            if (base) { mr->buf[mr->idx] = MAX_INT; live_runs--; }  // 首輪：用哨兵
            else { read_next_chunk_from_disk(); }                    // 後輪：續讀
        }
        adjust(runs, num_runs, ls[0]);  // 調整敗者樹
    }
    flush_remaining_buffer();
}

敗者樹調整 adjust() / create_loser_tree()

自下而上比較，失者上移，勝者繼續向上比較，最終 ls[0] 為全局最小記錄所在路索引。代碼極其緊湊高效。

五、實測性能數據

時間近似線性增長，驗證 O(N log K) 效率。

六、驗證排序結果

附帶 check.c 讀取二進制文件按 10 個/行打印，便於人工抽查有序性。