C 語言演算法實作：分治法之歸並排序完整指南

前言

歸並排序是分治法的另一經典應用，具有穩定 O(n log n) 時間複雜度、穩定排序特性，是外部排序與連結清單排序的首選。本文詳細解析自頂向下遞迴版、自底向上迭代版、自然歸並排序與 C++ 實作細節。

核心思想

1. 分：將 n 元素陣列對半分割為兩個 n/2 子陣列
2. 治：遞迴排序兩個子陣列
3. 合：將兩個有序子陣列合併為一個有序陣列

遞迴版實作（自頂向下）

偽代碼

MergeSort(A, left, right):
    if left < right:
        mid = (left + right) / 2
        MergeSort(A, left, mid)
        MergeSort(A, mid+1, right)
        Merge(A, left, mid, right)

合併函數

template <class T>
void Merge(T c[], T d[], int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    
    while (i <= m && j <= r) {
        if (c[i] <= c[j]) d[k++] = c[i++];
        else d[k++] = c[j++];
    }
    while (i <= m) d[k++] = c[i++];
    while (j <= r) d[k++] = c[j++];
}

完整遞迴實作

template <class T>
void MergeSort(T a[], int n) {
    T *b = new T[n];
    mergeSort(a, b, 0, n-1);
    delete[] b;
}

template <class T>
void mergeSort(T a[], T b[], int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, b, l, m);
    mergeSort(a, b, m+1, r);
    merge(a, b, l, m, r);
    copy(b + l, b + r + 1, a + l);  // 複製回原陣列
}

迭代版實作（自底向上）

核心思想

不使用遞迴，而是按段長 1、2、4、8... 依次合併相鄰有序段：

template <class T>
void MergeSort(T a[], int n) {
    T *b = new T[n];
    for (int seg = 1; seg < n; seg *= 2) {
        mergePass(a, b, seg, n);  // a → b
        seg *= 2;
        if (seg < n) mergePass(b, a, seg, n);  // b → a
    }
    delete[] b;
}

MergePass 函數

template <class T>
void mergePass(T x[], T y[], int seg, int n) {
    int i = 0;
    while (i <= n - 2*seg) {
        merge(x, y, i, i+seg-1, i+2*seg-1);
        i += 2*seg;
    }
    if (i + seg < n)  // 剩餘兩段不等長
        merge(x, y, i, i+seg-1, n-1);
    else  // 僅剩一段
        copy(x + i, x + n, y + i);
}

優點

• 無遞迴呼叫開銷，無棧溢位風險
• 記憶體存取模式連續，緩存友好
• 易於平行化（不同段獨立合併）

自然歸並排序

動機

利用輸入資料中已存在的有序子序列，減少合併輪數。

範例

輸入：[4, 8, 3, 7, 1, 5, 6, 2]

自然有序段：[4,8] [3,7] [1,5,6] [2] → 4 段

第 1 輪：[3,4,7,8] [1,2,5,6] → 2 段

第 2 輪：[1,2,3,4,5,6,7,8] → 完成

標準歸並需 3 輪（log₂8），自然歸並僅 2 輪。

極端情況

• 完全有序輸入：1 段，0 輪合併，O(n) 時間
• 完全逆序輸入：n 段，退化為標準歸並

複雜度分析

關鍵實作細節

1. 避免整數溢位

int mid = l + (r - l) / 2;  // 而非 (l+r)/2

2. 就地合併

標準歸並需要 O(n) 輔助空間。就地合併（In-place merge）可將空間降為 O(1)，但實作複雜且常數因子大，實務較少用。

3. 連結清單歸並

鏈結清單無需輔助陣列，合併時只需調整指標，空間 O(1)：

ListNode* merge(ListNode* a, ListNode* b) {
    ListNode dummy(0), *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) tail->next = a, a = a->next;
        else tail->next = b, b = b->next;
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

4. 外部排序應用

資料量超過記憶體時，歸並排序是標準解法：

1. 將資料分塊讀入記憶體，各自排序後寫回磁碟
2. 多路歸並合併排序後的檔案
3. 使用雙緩衝/非同步 I/O 重疊計算與傳輸

與其他排序比較

混合策略：Timsort

Python、Java、Android 使用的 Timsort 結合歸並與插入排序：

• 偵測自然有序段
• 短段用插入排序延伸
• 合併時用「膽量模式」優化
• 保證 O(n log n)，近乎有序資料達 O(n)

標準庫替代方案

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1, 9};
std::stable_sort(v.begin(), v.end());  // 保證穩定，通常用歸並排序

歸並排序以穩定、可預測的 O(n log n) 效能、天然適合外部排序與連結結構，成為排序演算法中的基石。理解其遞迴與迭代實作、自然歸並優化、以及與快速排序的權衡，是演算法工程師的必修功課。