Какие алгоритмы используют популярные компиляторы C ++ для std :: sort и std :: stable_sort? Я знаю, что стандарт дает только определенные требования к производительности, но я хотел бы знать, какие алгоритмы популярные реализации используют на практике.
Ответ был бы более полезным, если бы он приводил ссылки для каждой реализации.
Прежде всего: компиляторы не предоставляют любой реализация std::sort
, Хотя традиционно каждый компилятор поставляется в комплекте с реализацией стандартной библиотеки (которая в значительной степени зависит от встроенных компиляторов), теоретически вы можете поменять одну реализацию на другую. Один очень хороший пример — Clang компилирует как libstdc ++ (традиционно упакованный с gcc), так и libc ++ (совершенно новый).
Теперь, когда это вне пути …
std::sort
традиционно был реализован как интро сортировки. С точки зрения высокого уровня это означает относительно стандартную реализацию быстрой сортировки (с некоторым медианным зондированием, чтобы избежать O (n2) наихудший случай) в сочетании с процедурой сортировки для небольших входных данных. Реализация libc ++, однако, немного отличается и ближе к TimSort: она обнаруживает уже отсортированные последовательности во входных данных и избегает их повторной сортировки, что приводит к поведению O (n) на полностью отсортированном вводе. Он также использует оптимизированные сети сортировки для небольших входов.
std::stable_sort
с другой стороны, это более сложный характер. Это можно экстраполировать из самой формулировки Стандарта: сложность O (n log n) если может быть выделено достаточно дополнительной памяти (намекает на Сортировка слиянием), но вырождается в O (n log2 н) если нет.
Если мы возьмем в качестве примера gcc, то увидим, что он std::sort
и слияние для std::stable_sort
.
Если вы пройдете через код libc ++ вы увидите, что он также использует mergesort для std::stable_sort
если диапазон достаточно большой.
Также следует отметить, что, хотя общий подход всегда является одним из вышеупомянутых, они все высоко оптимизированы для различных особых случаев.