Какой алгоритм сортировки используется в GCC? - PullRequest
9 голосов
/ 28 августа 2011

С cplusplus.com std::sort Сложность определена:

Сложность

Приблизительно N * logN сравнений в среднем (где N является последним первым). В худшем случае, до N2, в зависимости от конкретного алгоритма сортировки, используемого при реализации библиотеки.

У меня есть некоторые ограничения во время выполнения моих приложений. Так что мне нужно знать, должен ли я реализовать свой собственный алгоритм сортировки, или это будет только пустая трата времени. Они скомпилированы с помощью gcc, поэтому мне нужно знать, какой алгоритм сортировки использует gcc.

1 Ответ

22 голосов
/ 28 августа 2011

GCC использует вариацию интросорт Musser . Это гарантирует наихудшее время работы O ( n log n ):

Он начинается с быстрой сортировки и переключается на heapsort, когда глубина рекурсии превышает уровень, основанный на ... количестве сортируемых элементов.

Реализация может быть найдена в заголовке stl_algo.h в функции __introsort_loop.

...