合併排序法 Merge Sort

C++ 合併排序法參考程式

合併排序使用分治法：先把陣列切小，再把排序好的子陣列合併回去。

• 遞迴把區間切成左右兩半，直到只剩一個元素。
• 合併時用一個 reg[] 暫存較小元素，最後把該區間複製回原陣列。
• 時間複雜度約為 O(n log n)，在大量資料時通常比 O(n²) 排序更有效率。

#include <iostream>
using namespace std;

void merge_sort_recursive(int a[], int reg[], int start, int end) {
    if (start >= end) return;

    int mid = (start + end) / 2;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;

    merge_sort_recursive(a, reg, start1, end1);
    merge_sort_recursive(a, reg, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2) {
        reg[k++] = (a[start1] <= a[start2]) ? a[start1++] : a[start2++];
    }

    while (start1 <= end1) reg[k++] = a[start1++];
    while (start2 <= end2) reg[k++] = a[start2++];

    // 把暫存區 reg 的結果寫回原陣列 a
    for (int i = start; i <= end; i++) {
        a[i] = reg[i];
    }
}

int main() {
    int data[] = {7, 2, 9, 1, 5, 3};
    int reg[6] = {0};
    int n = 6;

    merge_sort_recursive(data, reg, 0, n - 1);

    cout << "排序結果: ";
    for (int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
    cout << endl;

    return 0;
}