std::sort的底层实现算法是什么？
请深入分析std::sort的底层实现。它使用了哪种排序算法？为什么不用纯粹的快速排序？IntroSort是什么？什么情况下会退化为堆排序？
回答
古法程序员
std::sort的典型实现是IntroSort（内省排序）——结合三种算法：1)快速排序(主策略)、2)堆排序(递归深度超过2*logN时降级，防止O(n²)退化)、3)插入排序(当子序列长度小于阈值如16时，利用小数据量优势)。C++标准要求平均复杂度O(n log n)。libstdc++实现：先IntroSort主体，再对整体做一次插入排序(无需边界检查)。MSVC STL的std::sort部分场景使用改进版QS。注意：std::list不能使用std::sort（需随机迭代器），使用list::sort(归并排序)。C++17起可自定义执行策略如std::execution::par并行化。