merge_sort.cpp

// merge_sort.cpp
// -----------------------------------------------------------------
// Merge Sort（合併排序）
//
// 原理：分治法。把陣列對半切到只剩單一元素（天然有序），
//       再兩兩「合併」成有序的大段。
//
// 時間複雜度：最好 / 平均 / 最壞 都是 O(n log n)（穩定的效能保證）
// 空間複雜度：O(n)（需要輔助陣列）
// 穩定性：穩定
// 特點：適合鏈結串列與外部排序（磁碟大檔案）；
//       是 Tim Sort 的核心之一。
//
// Compile: g++ -std=c++17 -O2 -Wall -o merge_sort merge_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 合併 a[lo..mid] 與 a[mid+1..hi]（兩段各自有序）
static void merge(vector<int>& a, vector<int>& buf, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; ++k) buf[k] = a[k];
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; ++k) {
        if (i > mid)                a[k] = buf[j++];
        else if (j > hi)            a[k] = buf[i++];
        else if (buf[j] < buf[i])   a[k] = buf[j++];  // 嚴格小於 -> 穩定
        else                        a[k] = buf[i++];
    }
}

static void mergeSortRec(vector<int>& a, vector<int>& buf, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSortRec(a, buf, lo, mid);
    mergeSortRec(a, buf, mid + 1, hi);
    if (a[mid] <= a[mid + 1]) return;   // 已整體有序，跳過合併
    merge(a, buf, lo, mid, hi);
}

void mergeSort(vector<int>& a) {
    if (a.size() < 2) return;
    vector<int> buf(a.size());
    mergeSortRec(a, buf, 0, (int)a.size() - 1);
}

// 迭代（自底向上）版本：無遞迴，段寬 1, 2, 4, 8, ... 兩兩合併
void mergeSortBottomUp(vector<int>& a) {
    int n = (int)a.size();
    if (n < 2) return;
    vector<int> buf(n);
    for (int width = 1; width < n; width *= 2)
        for (int lo = 0; lo + width < n; lo += 2 * width)
            merge(a, buf, lo, lo + width - 1, min(lo + 2 * width - 1, n - 1));
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {38, 27, 43, 3, 9, 82, 10},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        mergeSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }

    vector<int> b = {9, 1, 8, 2, 7, 3, 6, 4, 5};
    printVec("bottom-up before: ", b);
    mergeSortBottomUp(b);
    printVec("bottom-up after : ", b);
    cout << "sorted : " << boolalpha << is_sorted(b.begin(), b.end()) << "\n";
    return 0;
}