C++ 歸並排序實現：左閉右開區間統一 STL 風格，基於《算法導論》改良

區間表示統一：左閉右開 [first, last)

《算法導論》使用 1-based 閉區間，C++ STL 採用 0-based 左閉右開。本實現全面採用 [p, r) 風格：

• 數組長度 n = r - p。
• 遞歸基例：p >= r - 1（0 或 1 元素）。
• 中點 q = p + (r - p) / 2，左半 [p, q)，右半 [q, r)。

合併邏輯：哨兵替代方案

原書用哨兵 INF 簡化合併，本實現用雙 while 循環處理剩餘元素，避免哨兵類型限制：

void merge(int* A, int p, int q, int r) { // 合併 [p, r)
    int n1 = q - p, n2 = r - q;
    int* L = new int[n1];
    int* R = new int[n2];
    for (int i = 0; i < n1; ++i) L[i] = A[p + i];
    for (int i = 0; i < n2; ++i) R[i] = A[q + i];
    int i = 0, j = 0, k = p;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }
    while (i < n1) A[k++] = L[i++];
    while (j < n2) A[k++] = R[j++];
    delete[] L; delete[] R;
}

遞歸入口

void merge_sort(int* a, int p, int r) { // 排序 [p, r)
    if (p < r - 1) {
        int q = p + (r - p) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q, r);
        merge(a, p, q, r);
    }
}
// 調用：merge_sort(arr, 0, n); // 而非 n-1

驗證與測試

• 對比 std::sort 結果，數萬組隨機數據通過。
• 邊界測試：空數組、單元素、已有序、逆序、大量重複值。
• 內存管理：new[]/delete[] 配對，無洩漏。

關鍵心得

1. 區間統一是避免下標錯誤的核心：始終維持循環不變量 [p, q) 和 [q, r)。
2. 左閉右開使長度計算、中點分割、邊界判斷極度統一，減少 +1/-1 心智負擔。
3. 合併時無哨兵雙 while更通用，適用於任意可比較類型。

擴展：模板化與迭代器版本

template <typename RandomIt>
void merge_sort(RandomIt first, RandomIt last) {
    if (last - first <= 1) return;
    auto mid = first + (last - first) / 2;
    merge_sort(first, mid);
    merge_sort(mid, last);
    std::inplace_merge(first, mid, last); // C++11 標準庫算法
}

生產代碼直接用 std::stable_sort 或 std::inplace_merge 實現的 merge_sort，手寫僅為教學驗證。