歸並排序：分治法、合並優化、插入排序混合、自底向上實現全解析

分治思想

將問題分解為子問題，遞歸求解，再合併。歸並排序：
1. 分解：數組對半分。
2. 解決：遞歸排序左右半。
3. 合併：將兩有序半數組合併為整體有序。

合併過程

雙指針遍歷左右有序區間，每次取較小元素放入輔助數組。需 O(n) 額外空間。
關鍵：合併時左/右區間已有序，線性掃描即可。

優化 1：避免多餘拷貝

合併後需拷回原數組。若左區間剩餘元素本來就在正確位置（右區間已空），無需拷貝。同理右區間。代碼中在合併循環結束後，只拷貝實際寫入輔助數組的部分。

優化 2：三數取中選主元（快排風格，此處不適用，歸並無主元）

歸並無主元選擇，但可優化葉子節點：

優化 3：小區間用插入排序

對長度 ≤ THRESHOLD（如 37）的區間直接插入排序，避免遞歸開銷。插入排序對近乎有序數據極快。
葉子「變粗」後，合併函數可簡化（保證左右區間長度 ≥ 2）。

優化 4：自底向上（非遞歸）

按寬度 2, 4, 8... 迭代合併相鄰區間。無遞歸開銷，但實測有時比遞歸慢（緩存/分支預測差異）。

代碼實現（綜合優化版 C++）

#include <bits/stdc++.h>
using namespace std;
const int INSERT_THRESHOLD = 37;
void insertion_sort(int* a, int n) {
    for (int i = 1; i < n; ++i) {
        int tmp = a[i], j = i;
        while (j > 0 && a[j-1] > tmp) a[j] = a[j-1], --j;
        a[j] = tmp;
    }
}
void merge(int* a, int* aux, int l, int m, int r) {
    int i = l, j = m, k = l;
    while (i < m && j < r) aux[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < m) aux[k++] = a[i++];
    while (j < r) aux[k++] = a[j++];
    // 只拷貝實際寫入範圍
    for (i = l; i < k; ++i) a[i] = aux[i];
}
void merge_sort_rec(int* a, int* aux, int l, int r) {
    if (r - l <= INSERT_THRESHOLD) {
        insertion_sort(a + l, r - l);
        return;
    }
    int m = l + (r - l) / 2;
    merge_sort_rec(a, aux, l, m);
    merge_sort_rec(a, aux, m, r);
    merge(a, aux, l, m, r);
}
void merge_sort(int* a, int n) {
    vector aux(n);
    merge_sort_rec(a, aux.data(), 0, n);
}
// 自底向上版
void merge_sort_bottom_up(int* a, int n) {
    vector aux(n);
    for (int w = 2; w < n; w <<= 1) {
        for (int i = 0; i < n; i += w) {
            int l = i, m = min(i + w/2, n), r = min(i + w, n);
            merge(a, aux.data(), l, m, r);
        }
    }
    // 最後可能剩餘區間 < w，再合併一次
    if (n > 1) merge(a, aux.data(), 0, n/2, n);
}

複雜度

• 時間：O(n log n) 最好/最壞/平均。
• 空間：O(n) 輔助數組。
• 穩定：相等元素保持相對順序（a[i] <= a[j]）。

關鍵點總結

• 歸並排序是分治法典型，穩定、性能穩健。
• 插入排序混合（閾值 8~64）是工程級優化標配（如 Java Arrays.sort、C++ std::sort 內部）。
• 自底向上消除遞歸，適合嵌入式/棧受限環境。
• 合併時避免多餘拷貝、利用哨兵簡化邊界檢查，可進一步提速。

深入理解歸並排序的各種優化，能寫出高性能、生產級的排序實現。