c++ - 为什么 std::sort 比手工编码的“introsort”更快？

Question

我使用快速排序、堆排序实现了 introsort。我的手工编码版本基于 D. Musser 的建议，递归深度切换到作为参数传递的堆排序，中位数为 3 枢轴选择。切换到简单插入排序的元素阈值为 16。

Answer 1

gcc 和 Microsoft 的 VisualC++ 都提供了 std::sort 的源代码（在头文件算法中）。所以，你可以自己看看。我以前研究过类似的问题。我的结论是，代码针对通用代码路径进行了优化，甚至使代码更加复杂和难以维护。对我来说有意义的权衡。