C++里的std::sort底层是用什么算法实现的？（内省排序Introsort结合快排与堆排）

std::sort采用内省排序（introsort），以quicksort为基线，递归过深时切heapsort，小数组用insertionsort优化，兼顾平均性能与O(n log n)最坏复杂度。

std::sort 用的是内省排序（introsort），不是纯快排

标准库实现不强制规定算法，但所有主流实现（GCC libstdc++、LLVM libc++、MSVC STL）都采用 introsort：它以 quicksort 为基线，在递归深度超限时切换到 heapsort，最后对小数组用 insertionsort 优化。这种组合是为了同时保证平均性能和最坏情况的 O(n log n) 时间界。

为什么不用纯快排？——最坏情况太危险

quicksort 在 pivot 选得极差时会退化到 O(n²)，比如已排序数组 + 固定取首/尾元素作 pivot。真实场景中，恶意输入或特定数据分布可能触发该路径。而 introsort 通过限制最大递归深度为 2 × floor(log₂ n) 来检测异常，一旦超限就切到 heapsort，彻底规避退化。

实际实现里还混了插入排序和分支预测优化

主流实现会在子数组长度 ≤ 某个阈值（如 GCC 是 16）时直接调用 insertionsort，因为小数组上它的常数项更优；同时，部分实现（如 libc++）还会在 partition 阶段用 __median_of_3 选 pivot，并加入分支预测提示（__builtin_expect）减少 pipeline stall。

• std::sort 不稳定，若需稳定排序请用 std::stable_sort
• 自定义比较函数必须满足严格弱序（strict weak ordering），否则行为未定义
• 迭代器必须是随机访问迭代器（RandomAccessIterator），std::list::sort 是特例，用的是归并

可以验证 introsort 行为的简单方式

虽然标准不暴露内部机制，但你可以构造一个深度可控的递归计数器 + 自定义 comparator 观察退化防护逻辑（注意：仅用于理解，勿在生产环境依赖）：

struct counting_comp {
    mutable int depth = 0;
    bool operator()(int a, int b) const {
       
 ++depth;
        return a < b;
    }
};

配合 std::vector 构造极端有序数据并反复调用 std::sort，你会发现 depth 增长被有效抑制——这就是 introsort 的深度保护在起作用。

真正要注意的是：别假设 pivot 策略或阈值，这些是实现细节；重点确保你的 Compare 对象无副作用、满足可传递性，否则连 O(n log n) 都无法保障。