歸併排序：分治法經典實現與 C 語言代碼詳解

歸併排序核心思想：分治法

歸併排序是「分治法」的教科書級應用。核心邏輯為三步走：

1. 分解：將長度為 n 的序列遞歸拆分為 n 個長度為 1 的有序子序列。
2. 解決：長度為 1 的序列天然有序。
3. 合併：將兩個有序子序列合併為一個有序序列（雙指針線性掃描），層層向上合併，最終得到完整有序序列。

此為「自頂向下」遞歸實現；亦可「自底向上」迭代實現（非遞歸版）。

合併操作核心邏輯

合併兩個有序陣列 sr[i..m] 與 sr[m+1..n] 至 tr[i..n]：

• 雙指針 i、j 分別指向兩子序列起始。
• 比較 sr[i] 與 sr[j]，較小者拷貝至 tr[k++]，對應指針後移。
• 某子序列耗盡後，將另一子序列剩餘元素批量拷貝至 tr。

C 語言完整實現代碼（遞歸版）

#include <stdio.h>
#include <stdlib.h>

void Merge(int sr[], int tr[], int i, int m, int n) {
    int j = m + 1, k = i;
    while (i <= m && j <= n)
        tr[k++] = (sr[i] < sr[j]) ? sr[i++] : sr[j++];
    while (i <= m) tr[k++] = sr[i++];
    while (j <= n) tr[k++] = sr[j++];
}

void MergeSort(int arr[], int arr1[], int s, int t) {
    if (s == t) {
        arr1[s] = arr[s];
    } else {
        int m = (s + t) / 2;
        int arr2[100];  // 臨時陣列，實際應動態分配或傳入全局緩衝區
        MergeSort(arr, arr2, s, m);
        MergeSort(arr, arr2, m + 1, t);
        Merge(arr2, arr1, s, m, t);
    }
}

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int arr1[100];
    printf("排序前：\n"); print(arr, n);
    MergeSort(arr, arr1, 0, n - 1);
    printf("排序後：\n"); print(arr1, n);
    return 0;
}

效能特性分析

關鍵優化方向

• 小區間插入排序：子序列長度 ≤ 閾值（如 16）時改用插入排序，減少遞歸開銷。
• 避免重複拷貝：雙緩衝區交替作為源/目標，或自底向上迭代版本省去遞歸棧。
• 就地合併：原地合併演算法（In-place Merge）可將空間降至 O(1)，但實現複雜且常數因子大，工程上較少用。
• 並行化：分治天然適合多線程/多進程並行，合併階段可併行。

總結

歸併排序以穩定的 O(n log n) 時間複雜度、優雅的分治結構、天然的並行友好特性，成為工業級排序庫（如 Java Arrays.sort、Python Timsort 核心組件）的基石。掌握其遞歸邊界、合併雙指針、空間權衡是演算法工程化的必修課。