C++ std::sort底层使用内省排序（Introsort）

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 函数。关键逻辑如下：

template
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²)，但它的运行路径（快排→堆排→插排）和比较次数仍取决于具体实现和输入规模，没法跨平台预测。