std::sort 实际采用内省排序：以快速排序起步，递归过深时切堆排序，小数组用插入排序，兼顾O(n log n)最坏复杂度与高平均性能。
std::sort 不是纯快速排序，而是内省排序（introsort）
标准库的 std::sort 在绝大多数实现（如 libstdc++、libc++）中用的是内省排序：它起步用快速排序，递归深度过深时切到堆排序，小数组则用插入排序。这不是“快排 + 优化”，而是一种混合策略，核心目标是**同时保证 O(n log n) 最坏复杂度和高平均性能**。
常见误解是看到“快排快”就以为底层就是快排——结果在某些特殊输入（比如已逆序的大数组）下，自己手写的快排爆栈或退化成 O(n²)，但 std::sort 依然稳如老狗，原因就在这层切换逻辑。
为什么不用纯快速排序？栈溢出和最坏性能是硬伤
纯递归快排最坏情况下（每次选到极值作 pivot）时间退化为 O(n²)，且递归深度可达 O(n)，容易触发栈溢出。内省排序通过监控递归深度（通常设为 ⌊log₂n⌋ × 2）来主动干预：
- 当当前递归深度超过阈值，立即放弃快排，改用
std::make_heap+std::sort_heap的堆排序路径 - 当子区间长度 ≤ 小阈值（通常是 16 或 32），直接调用插入排序——它对小数据局部性好、常数小、稳定（虽然
std::sort本身不保证稳定） - libstdc++ 中 pivot 选择不是简单取首/尾，而是用“三数取中”（median-of-3）再加随机扰动防恶意输入
不同 STL 实现的细节差异会影响性能表现
虽然标准只要求平均 O(n log n)、最坏 O(n log n)，但各实现的阈值、pivot 策略、fallback 时机并不统一：
立即学习“C++免费学习笔记（深入）”；
- libstdc++（GCC）：深度阈值为
2 * floor(log2(n))，小数组阈值为 16，插入排序前还会做一次“部分有序检测” - libc++（Clang）：深度阈值类似，但小数组阈值是 30，且插入排序前会先检查是否已基本有序（用
is_sorted_until） - MSVC STL：早期版本用 intro + 堆排，新版本引入了“pdqsort”启发式（更激进的分支判断，比如检测重复元素、单调段），但对外接口仍是
std::sort - 所有实现都**不保证稳定性**，要稳定请用
std::stable_sort（通常是归并排序）
你该关心的实际影响：什么时候会“意外变慢”或出错
多数人不会碰到底层算法细节，但以下情况会暴露内省排序的行为特征：
- 对
std::vector排 100 万个逆序数，std::sort仍 O(n log n)；但若你手写递归快排没设深度保护，可能栈溢出或超时 - 自定义类型排序时，如果
operator 有副作用或抛异常，内省排序的多次 pivot 比较 + fallback 切换会让行为更难预测（比如插入排序阶段又抛异常） - 用
std::sort排指针数组（std::vector）没问题，但别误以为它会对所指对象做任何操作——它只比较指针值 - 编译器优化等级（如
-O2）会影响内联和分支预测，进而让 pivot 选择、小数组路径的实际开销浮动，压测时别只看 debug 版
真正容易被忽略的点是：内省排序的“切换成本”几乎为零——它不额外分配内存，所有操作都在原容器上进行，但这也意味着你没法靠“打断排序过程”来获取中间状态；一旦调用 std::sort，就只能等它彻底结束。
