C 語言歸併排序演算法詳解與實作

演算法核心思想

歸併排序採用分治法：將陣列遞歸拆分至單元素，再兩兩合併為有序陣列。合併過程中，雙指標分別掃描兩個已排序子陣列，較小者優先寫入暫存陣列，最後複製回原陣列。

程式碼實作

#include 
#include 

#define M 6
#define N 4

int main() {
    int a[M] = {-3, 6, 19, 26, 68, 100};
    int b[N] = {8, 10, 12, 22};
    int c[M+N];
    int i = 0, j = 0, k = 0, l;

    printf("a 陣列元素:\n");
    for (l = 0; l < M; l++) printf("%d ", a[l]);
    printf("\nb 陣列元素:\n");
    for (l = 0; l < N; l++) printf("%d ", b[l]);

    /* 合併兩個已排序陣列 */
    while (i < M && j < N) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else              c[k++] = b[j++];
    }
    while (i < M) c[k++] = a[i++];
    while (j < N) c[k++] = b[j++];

    printf("\n合併後陣列:\n");
    for (l = 0; l < M+N; l++) printf("%d ", c[l]);
    return 0;
}

演示圖解

執行結果

完整版遞歸實作（單一陣列）

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

複雜度與特性

工程優化技巧

• 小區間切換插入排序：當子陣列長度 ≤ 16 時改用插入排序，減少遞歸開銷。
• 就地合併：旋轉演算法實現 O(1) 空間，但常數項大，實際較少用。
• 迭代式底向上：消除遞歸棧溢位風險，適合嵌入式環境。
• 自然歸併：利用資料中既有有序段，減少合併次數。