Какой тип сортировки используется в std :: sort ()?

Большинство реализаций std::sort используют quicksort (или обычно гибридный алгоритм, такой как introsort, который объединяет сортировку quicksort, heapsort и insertion).

Единственное, что требуется стандарту, это то, что std::sort каким- std::sort образом сортирует данные в соответствии с указанным порядком со сложностью приблизительно O (N log (N)); не гарантируется стабильность. Технически, introsort лучше отвечает требованиям сложности, чем quicksort, потому что quicksort имеет квадратичное худшее время.

Стандарт C ++ ISO / IEC 14882: 2003

25.3.1.1 сортировать

 template void sort(RandomAccessIterator first, RandomAccessIterator last); template void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 

1 Эффекты : Сортирует элементы в диапазоне [первый, последний].

2 Сложность : Приблизительно N log N (где N == последний – первый) сравнений в среднем.

Информация о методе отсутствует, но сложность всегда равна N log N

Существует три алгоритма, которые используются в STL MSVC2013, ссылаясь на исходный код std::sort .

Скорее всего, он использует QuickSort или вариант с IntroSort называемый IntroSort .

Если recursion идет слишком глубоко, HeapSort будет использоваться HeapSort .

В противном случае будет использоваться InsertSort .

Вероятно, все реализации std::sort используют introsort (aka introspection sort ), гибридный алгоритм, который объединяет quicksort и heapsort. Фактически, интросорт был особенно изобретен в 1997 году с целью реализации исполнительского сорта в C ++ STL.

Единственное, что требуется стандарту, это то, что std::sort каким- std::sort образом сортирует данные в соответствии с указанным порядком со сложностью O (N log (N)) ; он не гарантированно стабилен (имеется отдельный алгоритм std::stable_sort , если это потребуется).

Технически, introsort лучше отвечает требованиям сложности, чем quicksort: это потому, что heapsort гарантировал сложность O (N log (N)) в худшем случае, тогда как quicksort имеет квадратичное худшее время.

Тем не менее, heapsort «медленнее», чем quicksort в среднем случае, в том смысле, что heapsort выполняет C * N log (N), тогда как quicksort имеет производительность D * N log (n) , при этом D значительно меньше C (числа C и D – константы). Другими словами, накладные расходы по сравнению с предыдущим объемом выше, чем у быстрой сортировки.

Чтобы получить лучшее из обоих миров, introsort начинается с quicksort-рекурсивного алгоритма, но когда глубина рекурсии становится слишком высокой (что означает, что она попадает в вырожденное худшее поведение), она переключается на heapsort.

См. Также запись в Википедии для интросорта или оригинальной статьи Дэвида Муссера, который изобрел интросорт, особенно для STL.

Вы имеете в виду std :: sort? Если так, то это может быть реализовано любым способом. Вероятно, это Quick sort, но может быть radix или что-то еще. Пока он производит вам отсортированный список, по крайней мере, в O (n log n), реализация в порядке, afaik.

Только некоторые эмпирические результаты:

Я перевел скрипт python с использованием метода numpy 1.9.2 в C ++, используя std :: sort (VS2008 toolchain).

Я получаю только точные результаты в python и C ++, когда я использую аргумент numpy.sort kind = ‘mergesort’. Я получаю разные относительные упорядочения для элементов с одним ключом, когда kind = ‘quicksort’ или kind = ‘heapsort’. Поэтому я предполагаю, что по крайней мере для версии STL, которая поставляется с VS2008, std :: sort использует mergesort.