intro_sort.cpp

// intro_sort.cpp
// -----------------------------------------------------------------
// Intro Sort（內省排序）—— C++ std::sort 實際採用的演算法
//
// 原理：三種演算法的混合體，取各家之長：
//   1. Quick Sort 為主力（快、cache 友善）
//   2. 遞迴深度超過 2*log2(n) 時切換 Heap Sort（防 O(n^2) 退化）
//   3. 小區間（<= 16）用 Insertion Sort 收尾（小資料最快）
//
// 時間複雜度：最好 / 平均 / 最壞 都是 O(n log n)
// 空間複雜度：O(log n)
// 穩定性：不穩定
//
// Compile: g++ -std=c++17 -O2 -Wall -o intro_sort intro_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>

using namespace std;

static const int INSERTION_THRESHOLD = 16;

// ---------- 插入排序（區間版） ----------
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 siftDown(vector<int>& a, int lo, int n, int i) {
    while (true) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[lo + l] > a[lo + largest]) largest = l;
        if (r < n && a[lo + r] > a[lo + largest]) largest = r;
        if (largest == i) break;
        swap(a[lo + i], a[lo + largest]);
        i = largest;
    }
}
static void heapSortRange(vector<int>& a, int lo, int hi) {
    int n = hi - lo + 1;
    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, lo, n, i);
    for (int end = n - 1; end > 0; --end) {
        swap(a[lo], a[lo + end]);
        siftDown(a, lo, end, 0);
    }
}

// ---------- 三數取中 + Hoare partition ----------
static int medianOfThree(vector<int>& a, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo]) swap(a[mid], a[lo]);
    if (a[hi]  < a[lo]) swap(a[hi],  a[lo]);
    if (a[hi]  < a[mid]) swap(a[hi], a[mid]);
    return a[mid];                        // 中位數作 pivot
}

static int partition(vector<int>& a, int lo, int hi) {
    int pivot = medianOfThree(a, lo, hi);
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        swap(a[i], a[j]);
    }
}

// ---------- 主體：quick sort + 深度上限 ----------
static void introSortRec(vector<int>& a, int lo, int hi, int depthLimit) {
    while (hi - lo + 1 > INSERTION_THRESHOLD) {
        if (depthLimit == 0) {            // 遞迴太深 -> 堆排序保底
            heapSortRange(a, lo, hi);
            return;
        }
        --depthLimit;
        int p = partition(a, lo, hi);
        // 遞迴小半邊、迴圈大半邊（限制堆疊深度）
        if (p - lo < hi - p) {
            introSortRec(a, lo, p, depthLimit);
            lo = p + 1;
        } else {
            introSortRec(a, p + 1, hi, depthLimit);
            hi = p;
        }
    }
    insertionSortRange(a, lo, hi);        // 小區間插入排序收尾
}

void introSort(vector<int>& a) {
    if (a.size() < 2) return;
    int depthLimit = 2 * (int)log2((double)a.size());
    introSortRec(a, 0, (int)a.size() - 1, depthLimit);
}

int main() {
    // 一般案例
    vector<int> t1 = {24, 97, 40, 67, 88, 85, 15, 66, 53, 44, 26, 48, 16, 52, 45, 23, 90, 18, 49, 80};
    cout << "before: ";
    for (int x : t1) cout << x << " ";
    introSort(t1);
    cout << "\nafter : ";
    for (int x : t1) cout << x << " ";
    cout << "\nsorted : " << boolalpha << is_sorted(t1.begin(), t1.end()) << "\n\n";

    // 大型隨機測試 + 與 std::sort 對照
    mt19937 rng(42);
    vector<int> big(100000);
    for (int& x : big) x = (int)(rng() % 1000000);
    vector<int> ref = big;
    introSort(big);
    sort(ref.begin(), ref.end());
    cout << "100k random: match std::sort = " << boolalpha << (big == ref) << "\n";

    // 惡意輸入：已排序（傳統快排的最壞情況）
    vector<int> asc(50000);
    for (int i = 0; i < 50000; ++i) asc[i] = i;
    introSort(asc);
    cout << "50k ascending: sorted = " << is_sorted(asc.begin(), asc.end()) << "\n";

    // 全部相同
    vector<int> same(50000, 7);
    introSort(same);
    cout << "50k identical: sorted = " << is_sorted(same.begin(), same.end()) << "\n";
    return 0;
}