經典排序算法——歸並排序 C++ 實現與遞歸分治圖解

經典排序算法——歸並排序 C++ 實現與遞歸分治圖解

算法思想

分治法：將陣列二分遞歸排序，再合併兩個有序子陣列。
時間複雜度 O(n log n)（最好/最壞/平均），空間 O(n)，穩定排序。

遞歸流程圖解

[1,2,3,5,2,3]
      ↓ 分割
[1,2,3]   [5,2,3]
  ↓           ↓
[1,2] [3]   [5,2] [3]
 ↓    ↓      ↓    ↓
[1][2]     [5][2]   → 合併 → [1,2] [3] → [1,2,3]
                    → 合併 → [2,5] [3] → [2,3,5]
最終合併 → [1,2,2,3,3,5]

完整 C++ 代碼

#include 
#include 
using namespace std;

class MergeSort {
public:
    vector mergeSort(vector A) {
        if (A.size() < 2) return A;
        process(A, 0, A.size() - 1);
        return A;
    }
private:
    void process(vector &A, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        process(A, l, mid);
        process(A, mid + 1, r);
        merge(A, l, mid, r);
    }
    void merge(vector &A, int l, int mid, int r) {
        vector tmp(r - l + 1);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
            tmp[k++] = (A[i] < A[j]) ? A[i++] : A[j++];
        while (i <= mid) tmp[k++] = A[i++];
        while (j <= r)   tmp[k++] = A[j++];
        for (int t = 0; t < k; t++) A[l + t] = tmp[t];
    }
};

int main() {
    MergeSort ms;
    vector a = {1,2,3,5,2,3};
    auto sorted = ms.mergeSort(a);
    for (int x : sorted) cout << x << ' '; // 1 2 2 3 3 5
    return 0;
}

關鍵細節

1. mid = l + (r-l)/2 防溢位。
2. 合併用臨時陣列 tmp，避免覆蓋原數據。
3. 拷貝回原陣列時用索引 l+t 精確定位。
4. 穩定性來源：A[i] <= A[j] 時優先取左邊（代碼中 < 同理，相等取左）。

迭代版（自底向上）優化

void mergeSortIterative(vector &A) {
    int n = A.size();
    vector tmp(n);
    for (int width = 1; width < n; width <<= 1) {
        for (int l = 0; l < n; l += 2*width) {
            int mid = min(l + width - 1, n - 1);
            int r = min(l + 2*width - 1, n - 1);
            // merge [l,mid] [mid+1,r] into tmp, then copy back
        }
    }
}

迭代版無遞歸開銷，適合嵌入式/棧受限環境。

對比快速排序