前言
當數據量遠超內存（如 16 個數字、內存僅容 4 個）時，外部排序不可避免。兩大經典策略——**歸並排序**與**分佈排序（桶排序）**——各有千秋。本文以具體數字演示兩者流程、I/O 量、多核並行潛力與工程權衡。
測試數據
輸入 (16 數): 1 4 2 8 12 11 3 6 9 40 28 27 21 7 6 3
內存容量: 4 數
輸出目標: 1 2 3 3 4 6 6 7 8 9 11 12 21 27 28 40
策略一：歸並排序
三階段流程
- 分段：順序讀入 4 個數形成 4 個運行（Run），無 I/O（原地）。
- 內排序：每運行快排 → 4 個有序運行。
I/O：讀 16B + 寫 16B = **32 B**
- 多路歸並：敗者樹 / 優先隊列合併 4 路。
I/O：讀 16B + 寫 16B = **32 B**
總 I/O：64 B（2 次全數據掃描）
並行度分析
| 階段 | 可並行任務數 | 備註 |
|---|
| 分段 | 1 | 順序讀取 |
| 內排序 | 4 (Run 數) | 4 核心各排一 Run |
| 歸並 | 2 (雙向) | 頭尾向中間寫，需共享輸出緩衝區同步 |
**痛點**：最後階段歸並本質串行，難以充分利用多核；若 Run 數極大（如數千），需多趟歸並，I/O 放大。
策略二：分佈排序（桶排序）
兩階段流程
- 分桶：根據值域將 16 數分入 4 桶（每桶容 4 數）。
I/O：讀 16B + 寫 16B = **32 B**
- 桶內排序：各桶獨立快排，桶間天然有序。
I/O：讀 16B + 寫 16B = **32 B**
總 I/O：64 B（同歸並）
並行度分析
| 階段 | 可並行任務數 | 備註 |
|---|
| 分桶 | 4 (桶數) | 4 核心各寫一桶文件 |
| 桶內排序 | 4 (桶數) | 4 核心各排一桶，無同步 |
**優勢**：全流程**無全局同步點**，自然適合多核/分佈式（MapReduce Shuffle 即分佈排序）。
核心難點：桶劃分均勻性
- 需預先掃描或估算值域分佈（直方圖/樣本）。
- 傾斜數據導致某桶溢出 → 溢出桶遞歸處理或動態分裂。
- 工程上常用 **T-digest / HDR 直方圖** 近似分位數劃分桶邊界。
綜合對比表
| 維度 | 歸並排序 | 分佈排序 |
|---|
| I/O 總量 | 2N (雙趟) | 2N (雙趟) |
| 最大並行度 | Run 數 (早期) → 2 (歸並期) | 桶數 (全程) |
| 實現複雜度 | 低 (成熟庫支援) | 中 (需桶劃分策略) |
| 數據傾斜敏感度 | 低 | 高 (核心風險) |
| 適用場景 | 通用、Run 數可控、單機 | 大規模、分佈式、多核、值域可估 |
| 代表系統 | STL `std::inplace_merge`、数据库外排、Hadoop MapReduce (Sort 阶段) | Hadoop Shuffle、Spark PartitionBy、ClickHouse 外表排序 |
工程選型建議
- 單機、數據量 ≤ 幾百 GB、Run 數 ≤ 100：直接用歸並排序（`sort -T /tmp` / 數據庫 `ORDER BY`）。
- 叢集、TB 級、需水平擴展：分佈排序（MapReduce/Spark/Flink 原生）。
- 混合方案：Map 端本地歸並生成有序 Run → Shuffle 以分佈排序分區 → Reduce 端歸並合併（即 MapReduce/Spark 排序流程）。
參考文獻
- Knuth, *The Art of Computer Programming, Vol. 3: Sorting and Searching*, Ch. 5.4 (External Sorting)
- 《數據密集型應用系統設計》Ch. 3 (Sorting and Merging)
- Hadoop `MapOutputBuffer` / Spark `ExternalSorter` 源碼
