std::sort底层采用内省排序（Introsort）：小数组用插入排序，递归过深时切堆排序，兼顾性能与最坏O(n log n)保障；主流实现（libstdc++、libc++、MSVC）均如此，但标准仅规定复杂度，未强制算法。
std::sort 用的是内省排序（Introsort）
标准库的 std::sort 在绝大多数主流实现（如 libstdc++、libc++、MSVC STL）中，底层确实是 内省排序——它不是单一算法，而是 introsort：在快速排序递归深度超过阈值时，自动切换到堆排序；对小数组（通常 ≤16 或 ≤32 元素）则改用插入排序。这种组合是为了兼顾平均性能、最坏情况保障和小数据常数开销。
为什么不用纯快排或纯堆排？
纯快速排序最坏时间复杂度是 O(n²)（比如已排序数组+固定轴点），而堆排序稳定 O(n log n) 但常数大、缓存不友好；插入排序对小数组实际更快。内省排序通过监测递归深度（一般设为 2 × floor(log₂ n)）来防退化，一旦超限就切到堆排序，从而保证最坏也是 O(n log n)。
-
libstdc++（GCC）：用std::__introsort_loop实现，深度阈值为2 * std::__lg(__last - __first) -
libc++（Clang）：同样基于 introsort，小数组阈值为 30，深度限制为2 * __lg(__last - __first) - MSVC STL：也采用 introsort，小数组用插入排序，递归深度超限时转堆排序
你不能依赖具体实现，但可以观察行为
标准只规定 std::sort 必须是 O(n log n) 平均与最坏复杂度，且是“不稳定排序”；它没强制要求用 introsort——理论上某实现用 timsort 也合法（只要满足复杂度和稳定性约束）。但现实中所有主流实现都选 introsort，因为它是工程上最平衡的选择。
- 无法通过代码直接调用
introsort函数——它只是内部实现细节，不在标准接口里 - 如果需要确定性行为（比如调试/测试），不要假设分区点或比较次数；应避免依赖排序中间状态
- 自定义比较器必须满足严格弱序（strict weak ordering），否则内省排序可能崩溃或无限循环
想验证？看 GCC 的 libstdc++ 源码片段
在 bits/stl_algo.h 中，std::sort 最终会进入 __introsort_loop 函数。关键逻辑如下：
可完全访问 Exchange 2010 EWS，管理邮件、文件夹、附件、日历事件、联系人、任务及外出设置。
立即学习“C++免费学习笔记（深入）”；
template<typename _RandomAccessIterator, typename _Size>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __max_depth)
{
while (__last - __first > int(_S_threshold))
{
if (__max_depth == 0)
{
std::__partial_sort(__first, __last, __last); // 堆排序入口
return;
}
--__max_depth;
_RandomAccessIterator __cut =
std::__unguarded_partition(__first, __last,
std::__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1)));
__introsort_loop(__cut, __last, __max_depth);
__last = __cut;
}
std::__insertion_sort(__first, __last); // 小数组走插入
}
注意：_S_threshold 通常是 16，__median 选三数中位数做 pivot，__unguarded_partition 是无边界检查的分区——这些全是 introsort 典型特征。
真正容易被忽略的是：哪怕你传入完全有序的数组，std::sort 也不会退化成 O(n²)，但它的运行路径（快排→堆排→插排）和比较次数仍取决于具体实现和输入规模，没法跨平台预测。
