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 观察退化防护逻辑（注意：仅用于理解，勿在生产环境依赖）：
立即学习“C++免费学习笔记（深入）”；
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) 都无法保障。
