歸併排序演算法 C++ 完整實作與分治法原理圖解

歸併排序是分治法經典應用，時間複雜度穩定 O(N log N)。本文提供標準 C++ 實作、關鍵合併邏輯圖解、空間複雜度分析與優化方向。

核心思想

1. 分解：遞迴將陣列對半分割，直到單元素（天然有序）。
2. 合併：將兩個有序子陣列合併為一個有序陣列。

合併邏輯圖解

左半部: [2, 5, 8]   右半部: [1, 3, 9]
索引 i=0, j=0
比較 2 vs 1 → 取 1, j++
比較 2 vs 3 → 取 2, i++
比較 5 vs 3 → 取 3, j++
比較 5 vs 9 → 取 5, i++
比較 8 vs 9 → 取 8, i++
左半部耗盡 → 直接複製右半部剩餘 9
結果: [1, 2, 3, 5, 8, 9]

標準 C++ 實作

#include <iostream>
using namespace std;

// 合併兩個有序子陣列 a[first..mid] 和 a[mid+1..last]
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1, k = 0;
    while (i <= mid && j <= last) {
        temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= last) temp[k++] = a[j++];
    for (i = 0; i < k; ++i) a[first + i] = temp[i];
}

void mergeSort(int a[], int first, int last, int temp[]) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergeSort(a, first, mid, temp);
        mergeSort(a, mid + 1, last, temp);
        mergeArray(a, first, mid, last, temp);
    }
}

bool MergeSort(int a[], int n) {
    int *temp = new (nothrow) int[n];
    if (!temp) return false;
    mergeSort(a, 0, n - 1, temp);
    delete[] temp;
    return true;
}

int main() {
    int arr[] = {2, 1, 4};
    MergeSort(arr, 3);
    for (int v : arr) cout << v << ' ';  // 1 2 4
}

複雜度分析

優化方向

1. 自底向上迭代版：避免遞迴呼叫開銷，適合嵌入式環境。
2. 小區間改用插入排序：當子陣列長度 < 閾值（如 16）時切換，減少函式呼叫。
3. 原地歸併：極度優化空間至 O(1)，但實作複雜且常數因子大，工程上較少用。
4. 並行化：分治天然適合多執行緒，OpenMP/C++17 parallel algorithms 易於平行化。

總結

歸併排序以穩定 O(N log N) 時間、簡潔邏輯、易於並行化，成為外部排序、連結串列排序、倒數對計算等場景首選。掌握其合併核心邏輯，是演算法面試與工程實踐的基本功。