tim_sort.cpp

// tim_sort.cpp
// -----------------------------------------------------------------
// Tim Sort（簡化版）—— Python sorted() / Java Arrays.sort(Object[]) 採用
//
// 原理：Merge Sort + Insertion Sort 的混合，充分利用真實資料
//       常見的「已部分有序」特性：
//   1. 把陣列切成固定大小的 run（本檔 RUN=32），
//      每個 run 用插入排序排好（小區間插入排序最快）。
//   2. 以 32, 64, 128... 的寬度自底向上兩兩合併。
//   （完整版 TimSort 還有：偵測自然 run、galloping、run 堆疊平衡等）
//
// 時間複雜度：最好 O(n)（資料已排序）
//             平均 / 最壞 O(n log n)
// 空間複雜度：O(n)
// 穩定性：穩定
//
// Compile: g++ -std=c++17 -O2 -Wall -o tim_sort tim_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

static const int RUN = 32;

static void insertionSortRange(vector<int>& a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; ++i) {
        int key = a[i], j = i - 1;
        while (j >= lo && a[j] > key) { a[j + 1] = a[j]; --j; }
        a[j + 1] = key;
    }
}

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++];
    }
}

void timSort(vector<int>& a) {
    int n = (int)a.size();
    if (n < 2) return;

    // 1. 每個 RUN 區間先用插入排序
    for (int lo = 0; lo < n; lo += RUN)
        insertionSortRange(a, lo, min(lo + RUN - 1, n - 1));

    // 2. 自底向上合併：寬度 32, 64, 128, ...
    vector<int> buf(n);
    for (int width = RUN; width < n; width *= 2) {
        for (int lo = 0; lo + width < n; lo += 2 * width) {
            int mid = lo + width - 1;
            int hi  = min(lo + 2 * width - 1, n - 1);
            if (a[mid] > a[mid + 1])          // 已整體有序則跳過
                merge(a, buf, lo, mid, hi);
        }
    }
}

int main() {
    vector<int> t1 = {5, 21, 7, 23, 19, 10, 12, 42, 3, 0, -8, 15, 2};
    cout << "before: ";
    for (int x : t1) cout << x << " ";
    timSort(t1);
    cout << "\nafter : ";
    for (int x : t1) cout << x << " ";
    cout << "\nsorted : " << boolalpha << is_sorted(t1.begin(), t1.end()) << "\n\n";

    // 大型測試 + 與 std::stable_sort 對照
    mt19937 rng(7);
    vector<int> big(200000);
    for (int& x : big) x = (int)(rng() % 100000);
    vector<int> ref = big;
    timSort(big);
    stable_sort(ref.begin(), ref.end());
    cout << "200k random: match stable_sort = " << boolalpha << (big == ref) << "\n";

    // 部分有序資料（TimSort 的強項）
    vector<int> partial(100000);
    for (int i = 0; i < 100000; ++i) partial[i] = i;
    for (int i = 0; i < 100; ++i)                     // 打亂 100 處
        swap(partial[rng() % 100000], partial[rng() % 100000]);
    timSort(partial);
    cout << "100k nearly-sorted: sorted = "
         << is_sorted(partial.begin(), partial.end()) << "\n";

    vector<int> empty_v, single = {42};
    timSort(empty_v); timSort(single);
    cout << "edge cases OK\n";
    return 0;
}