C++ std::sort 內部實現解析：內省排序與三階段混合策略

C++ std::sort 內部實現解析：內省排序與三階段混合策略

std::sort 是 C++ 標準庫中最常用的排序算法，標準要求最壞情況 O(N log N)，但未強制具體實現。主流標準庫（libstdc++, libc++, MSVC STL）均採用內省排序作為核心，輔以插入排序優化小區間。

內省排序三階段混合

1. 快速排序：主力階段，隨機選樞軸或中位數三數取中，避免最壞 O(N^2)；
2. 堆排序：當遞歸深度超過 2 log2(N) 時切換，保證最壞 O(N log N)；
3. 插入排序：區間長度 ≤ 16~32 時切換，低常數因子極快。

GCC libstdc++ 實現鏈路

// 入口
template
void sort(RandomIt first, RandomIt last, Compare comp) {
    if (first != last) {
        std::__introsort_loop(first, last, std::__lg(last-first)*2, comp);
        std::__final_insertion_sort(first, last, comp);
    }
}

// 核心循環
template
void __introsort_loop(RandomIt first, RandomIt last, Size depth_limit, Compare comp) {
    while (last - first > _S_threshold) {          // _S_threshold = 16
        if (depth_limit == 0) {
            std::make_heap(first, last, comp);
            std::sort_heap(first, last, comp);
            return;
        }
        --depth_limit;
        RandomIt pivot = std::__partition_pivot(first, last, comp);
        // 遞歸處理較大分區，迭代處理較小分區（尾遞歸優化）
        if (pivot - first < last - pivot) {
            __introsort_loop(first, pivot, depth_limit, comp);
            first = pivot + 1;
        } else {
            __introsort_loop(pivot + 1, last, depth_limit, comp);
            last = pivot;
        }
    }
}

// 最後插入排序收尾
template
void __final_insertion_sort(RandomIt first, RandomIt last, Compare comp) {
    for (RandomIt i = first + 1; i != last; ++i)
        for (RandomIt j = i; j != first && comp(*j, *(j-1)); --j)
            iter_swap(j, j-1);
}

關鍵設計細節

• 樞軸選取：__median_pivot 取首、中、末三者中位數，極大降低惡化概率；
• 深度限制：2 * log2(N)，超限轉堆排序；
• 尾遞歸消除：迭代處理較大分區，遞歸處理較小分區，棧深度 O(log N)；
• 插入排序閾值：_S_threshold = 16（GCC），32（MSVC），經實驗調優。

使用指南與避坑

簡易測試代碼

#include <algorithm>, <iostream>, <vector>, <random>
using namespace std;

struct Whatever {
    int size; char name;
    bool operator<(const Whatever& o) const { return size < o.size; }
};

int main() {
    vector v = {12,10,13,15,20,18,11};
    sort(v.begin(), v.end());                 // 升序
    sort(v.begin(), v.end(), greater<>());    // 降序

    vector vw;
    mt19937 rng(random_device{}());
    uniform_int_distribution dist(0,49);
    for (int i=0;i<100;++i) vw.push_back({dist(rng), char('a'+rng()%26)});
    sort(vw.begin(), vw.end(), [](auto& a, auto& b){ return a.size < b.size; });
}

總結

std::sort 通過「快速排序主力 + 堆排序兜底 + 插入排序收尾」三重保障，在工程實踐中達到平均最快、最壞有保證、小數據極優的綜合最優表現。理解其內部機制有助於在性能敏感場景做出正確選型（如是否需要 stable_sort、是否啟用並行版本）。