在GCC中使用哪种排序算法？

Question

来自cplusplus.com的 std::sort复杂性定义如下:

复杂

平均大约N*logN比较(其中N是最后一个).在最坏的情况下,最多N2,取决于库实现使用的特定排序算法.

我的应用程序运行时间有一些限制.所以我需要知道我是否应该实现自己的排序算法,否则只会浪费时间.它们是用gcc编译的,所以我需要知道gcc使用哪种排序算法.

Answer 1

海湾合作委员会使用Musser's introsort的变种.这可以保证最坏情况下的运行时间为O(n log n):

它以快速排序开始,并在递归深度超过基于...被排序的元素数量的级别时切换到堆.

可以在函数的stl_algo.h标题中找到实现__introsort_loop.