歸併排序是穩定、分治、O(n log n) 最壞情況保證、非原地 (需 O(n) 輔助空間) 的經典算法。本文從核心合併邏輯、自頂向下遞歸 vs 自底向上迭代、輔助空間優化、自然歸併、外部排序擴展、工程級測試策略**六大維度，構建完整認知體系。
合併兩個有序子數組 arr[lo..mid] 和 arr[mid+1..hi] 至輔助數組 aux，再拷回。關鍵點：雙指針 i, j，比較 arr[i] <= arr[j] 保證穩定性 (等於時取左側)。
static void merge(int arr[], int aux[], int lo, int mid, int hi) {
// 拷貝到輔助數組 (或直接雙指針讀原數組寫 aux)
for (int k = lo; k <= hi; k++) aux[k] = arr[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = aux[j++]; // 左半耗盡
else if (j > hi) arr[k] = aux[i++]; // 右半耗盡
else if (aux[i] <= aux[j]) arr[k] = aux[i++]; // 穩定：<= 取左
else arr[k] = aux[j++];
}
}
void merge_sort_recursive(int arr[], int n) {
if (!arr || n <= 1) return;
int *aux = malloc(n * sizeof(int));
_merge_sort(arr, aux, 0, n - 1);
free(aux);
}
static void _merge_sort(int arr[], int aux[], int lo, int hi) {
if (lo >= hi) return;
int mid = lo + ((hi - lo) >> 1);
_merge_sort(arr, aux, lo, mid);
_merge_sort(arr, aux, mid + 1, hi);
merge(arr, aux, lo, mid, hi);
}
遞歸深度：O(log n)，棧空間安全。
子數組大小 sz 從 1, 2, 4, 8... 翻倍，兩兩合併。
void merge_sort_iterative(int arr[], int n) {
if (!arr || n <= 1) return;
int *aux = malloc(n * sizeof(int));
for (int sz = 1; sz < n; sz <<= 1) {
for (int lo = 0; lo < n - sz; lo += sz << 1) {
int mid = lo + sz - 1;
int hi = (mid + sz < n) ? mid + sz : n - 1;
merge(arr, aux, lo, mid, hi);
}
}
free(aux);
}
優勢：無函數調用開銷、順序訪問內存 (預取友好)、天然適合多線程 (每層獨立任務)。
| 技巧 | 原理 | 代價/限制 |
|---|---|---|
| 單一輔助數組 | 頂層分配一次 aux[n]，遞歸傳遞 | 標準做法，O(n) 額外空間 |
| 雙緩衝交換 | 遞歸層級奇偶交換 arr 和 aux 角色，最終若結果在 aux 則拷回 | 省去合併後的 memcpy 回寫，但代碼複雜 |
| 原地歸併 | 旋轉算法/塊交換實現 O(1) 空間合併 | 極其複雜，常數因子大，教學/研究價值 > 工程 |
掃描數組識別天然遞增段 (Run)，將 Run 視為初始合併單元。對近乎有序數據極快 (接近 O(n))。TimSort (Python/Java sort()) 核心基石。
數據量超內存 (如 100GB 文件，內存 4GB)：
| 類別 | 用例 | 驗證點 |
|---|---|---|
| 邊界 | NULL, 0, 1, 2 元素 | 參數檢查、基線條件 |
| 有序性 | 升序、降序、鋸齒序列 | 合併邏輯正確性 |
| 穩定性 | 結構體 {key, id}，相同 key 檢查 id 相對序 | 必通過 (歸併核心優勢) |
| 重複鍵 | 大量重複、全等 | 合併邊界條件 (j>hi 等) |
| 大規模 | 10⁵/10⁶ 隨機數，對比 std::stable_sort | 性能基準、內存佔用 |
| 外部排序 | 生成 2x 內存大小文件，驗證輸出有序 | 多路歸併、臨時文件清理 |
| 維度 | 快速排序 | 歸併排序 |
|---|---|---|
| 分治順序 | 先分區 (Partition) → 遞歸 | 先遞歸 → 後合併 (Merge) |
| 空間複雜度 | O(log n) 棧 (原地) | O(n) 輔助數組 |
| 穩定性 | 不穩定 | 穩定 |
| 最壞時間 | O(n²) (可隨機化避免) | O(n log n) 保證 |
| 緩存局部性 | 優 (原地分區) | 一般 (需輔助數組) |
| 並行化 | 分區後獨立，但負載不均 | 層級並行天然均衡 |
| 外部排序 | 不適用 | 標準方案 |
歸併排序以「先遞歸分解至原子，再線性合併構建有序」的優雅分治邏輯，提供了穩定性與最壯時間保證的雙重承諾。掌握雙指針合併、自底向上迭代、外部排序多路歸併三大核心技術，是處理海量數據、構建穩定排序組件、理解 TimSort/IntroSort 混合算法的必經之路。
