分治法與歸並排序：原理、代碼與遞歸追蹤

分治策略

分治模式在每層遞歸包含三步：

1. 分解：將原問題分解為子問題。
2. 解決：遞歸求解子問題，足夠小時直接求解。
3. 合並：將子問題解合併為原問題解。

歸並排序核心：合並兩個有序子序列

模擬撲克牌合併：兩堆有序牌，每次取較小的一張放桌面，直到一堆空，再將剩餘牌依次放下。

void merge(int ar[], int p, int q, int r, int temp[]) {
    int i = p, j = q + 1, k = 0;
    while (i <= q && j <= r)
        temp[k++] = (ar[i] < ar[j]) ? ar[i++] : ar[j++];
    while (i <= q) temp[k++] = ar[i++];
    while (j <= r) temp[k++] = ar[j++];
    for (k = 0; k <= r - p; k++) ar[p + k] = temp[k];
}

利用分治使原序列有序

遞歸二分直到單元素，再逐層合並：

void mergesort(int ar[], int head, int end, int temp[]) {
    if (head < end) {
        int mid = (head + end) / 2;
        mergesort(ar, head, mid, temp);
        mergesort(ar, mid + 1, end, temp);
        merge(ar, head, mid, end, temp);
    }
}

完整代碼（兩個版本）

版本 1：基礎版

#include <stdio.h>, <stdlib.h>, <conio.h>, <time.h>

void mergesort(int [], int, int, int []);
void merge(int [], int, int, int, int []);

int main() {
    int *ar = malloc(10 * sizeof(int)), *temp = malloc(10 * sizeof(int));
    srand(time(NULL));
    for (int i=0; i<10; i++) { ar[i] = rand()%1000; printf("%-4d", ar[i]); }
    mergesort(ar, 0, 9, temp);
    printf("\n歸並排序後:\n");
    for (int i=0; i<10; i++) printf("%-4d", ar[i]);
    free(temp); free(ar); _getch(); return 0;
}

void mergesort(int ar[], int head, int end, int temp[]) { ... }
void merge(int ar[], int p, int q, int r, int temp[]) { ... }

版本 2：帶入口函數，更通用

void mergesort(float *ar, int size) {
    if (size > 0) {
        float *temp = malloc(size * sizeof(float));
        _mergesort(ar, 0, size - 1, temp);
        free(temp);
    }
}
void _mergesort(float *ar, int head, int end, float *temp) { ... }
void merge(float *ar, int p, int q, int r, float *temp) { ... }

主程序只需調用 mergesort(ar, n)，內部自動管理臨時數組。

複雜度與特性

• 時間複雜度：O(n log n)（最好/最壞/平均）。
• 空間複雜度：O(n) 輔助數組。
• 穩定排序：相等元素相對順序不變。
• 適用於鏈表（無需隨機訪問）及外部排序。