歸並排序 C 語言完整實作與圖解分析

演算法核心思想

歸並排序採用 分治法：

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

時間複雜度穩定 O(n log n)，空間複雜度 O(n)，屬穩定排序。

合併操作詳細流程

void Merge(int array[], int left, int mid, int right) {
    int aux[Max_] = {0};          // 暫存陣列
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (array[i] < array[j]) aux[k++] = array[i++];
        else                     aux[k++] = array[j++];
    }
    while (i <= mid) aux[k++] = array[i++];
    while (j <= right) aux[k++] = array[j++];

    for (i = left, k = 0; i <= right; i++, k++)
        array[i] = aux[k];
}

遞迴主程序

void MergeSort(int array[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        MergeSort(array, start, mid);
        MergeSort(array, mid + 1, end);
        Merge(array, start, mid, end);
    }
}

完整可執行程式

#include 
#define MAX_N 10

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

int main() {
    int arr[MAX_N] = {8, 4, 2, 3, 5, 1, 6, 9, 0, 7};
    printf("排序前: "); Show(arr, MAX_N);
    MergeSort(arr, 0, MAX_N - 1);
    printf("排序後: "); Show(arr, MAX_N);
    return 0;
}

效能優化方向

• 閾值切換：小規模（如 ≤ 32）改用插入排序，減少遞迴開銷。
• 就地合併：原地合併演算法（In-place merge）可省略輔助陣列，但實作複雜且常數因子大。
• 迭代版本：自底向上迭代避免遞迴堆疊溢位風險。
• 並行化：分治結構天然適合多執行緒，OpenMP 只需在遞迴呼叫前加 #pragma omp task。

常見錯誤與除錯技巧