非遞歸歸並排序實現：自底向上迭代，穩定排序 5000 萬整數

歸並排序的非遞歸優勢

• **天然穩定排序**（相等元素相對順序不變）。
• **最壞/平均/最好均為 O(N log N)**，無快排最壞 O(N²) 風險。
• 非遞歸版採用**自底向上**迭代，無棧溢出風險，記憶體訪問極其順序（緩存友好）。

核心思路：步長倍增法

將陣列視為長度為 step 的有序子段，step = 1, 2, 4, 8... 依次兩兩歸並，直到 step >= N。

完整實現 (C 風格，測試 5000 萬 int 穩定)

#include <stdlib.h>
#include <string.h> // memcpy

void MergeSort(int *arr, unsigned int n) {
    if (n < 2) return;

    int *tmp = (int*)malloc(n * sizeof(int));
    if (!tmp) return;

    for (unsigned int step = 1; step < n; step <<= 1) {
        unsigned int left_start = 0;
        while (left_start < n) {
            unsigned int mid = left_start + step;
            if (mid >= n) { // 剩餘單段，直接複製
                memcpy(tmp + left_start, arr + left_start, (n - left_start) * sizeof(int));
                break;
            }
            unsigned int right_end = mid + step;
            if (right_end > n) right_end = n;

            // 歸並 [left_start, mid) 和 [mid, right_end) 到 tmp
            unsigned int i = left_start, j = mid, k = left_start;
            while (i < mid && j < right_end) {
                tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i < mid) tmp[k++] = arr[i++];
            while (j < right_end) tmp[k++] = arr[j++];

            left_start = right_end;
        }
        // tmp 回寫 arr（或雙緩衝交換指標避免 memcpy）
        memcpy(arr, tmp, n * sizeof(int));
    }
    free(tmp);
}

關鍵優化細節

1. 雙緩衝指標交換（消除 memcpy）： 用 int *src = arr, *dst = tmp; 每輪歸並後 swap(src, dst); 最後若 src != arr 再 memcpy 一次。可節省 50% 複製開銷。
2. 小段插入排序啟動： step=1 前先對長度 16-32 的小段做插入排序，減少歸並輪數。
3. 就地歸並： 極其複雜且常數大，工程上不推薦，外部 O(N) 空間完全可接受。
4. 並行化潛力： 每輪不同區間歸並互不干擾，極易用 OpenMP #pragma omp parallel for 平行化。

雙緩衝優化版核心片段

int *src = arr, *dst = tmp;
for (unsigned int step = 1; step < n; step <<= 1) {
    for (unsigned int left = 0; left < n; left += 2*step) {
        unsigned int mid = left + step;
        if (mid >= n) { // 剩餘段直接複製
            memcpy(dst + left, src + left, (n - left) * sizeof(int));
            break;
        }
        unsigned int right = mid + step;
        if (right > n) right = n;

        unsigned int i = left, j = mid, k = left;
        while (i < mid && j < right)
            dst[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
        while (i < mid) dst[k++] = src[i++];
        while (j < right) dst[k++] = src[j++];
    }
    int *t = src; src = dst; dst = t; // 指標交換
}
if (src != arr) memcpy(arr, src, n * sizeof(int)); // 最後可能需回寫

測試結果對比 (5000 萬 int, 隨機數)

適用場景總結

• **需要穩定排序**（如多關鍵字排序：先按姓名、再按年齡）。
• **鏈表排序**（歸並只需指標操作，O(1) 空間）。
• **外部排序**（檔案超大，磁盤順序讀寫）。
• **近乎有序數據**（自然歸並優化可達 O(N)）。

非遞歸歸並排序以簡潔的迭代邏輯、保證的 O(N log N) 性能、天然穩定性與極佳的緩存局部性，成為海量數據、穩定排序、外部排序的首選演算法。