Какой алгоритм сортировки используется STL's list :: sort ()?

Question

У меня есть список случайных целых чисел. Мне интересно, какой алгоритм используется методом list::sort(). Например. в следующем коде:

list<int> mylist;

// ..insert a million values

mylist.sort();

РЕДАКТИРОВАТЬ: См. Также этот более конкретный вопрос .

Answer 1

Стандарт не требует определенного алгоритма, он только должен быть стабильным и выполнять сортировку, используя приблизительно N lg N сравнений. Это позволяет, например, сортировку слиянием или версию со связанным списком быстрой сортировки (вопреки распространенному мнению, быстрая сортировка не является обязательно нестабильной, даже если самая распространенная реализация для массивов) .

С этой оговоркой, краткий ответ заключается в том, что в большинстве современных стандартных библиотек std::sort реализован как интросортировка (интроспективная сортировка), которая в основном является быстрой сортировкой, которая отслеживает глубину рекурсии и переключается на Heapsort (обычно медленнее, но с гарантированной сложностью O (n log n)), если Quicksort использует слишком глубокую рекурсию. Интросорт был изобретен сравнительно недавно (конец 1990-х годов). В старых стандартных библиотеках обычно использовалась быстрая сортировка.

stable_sort существует, потому что для сортировки массивов-подобных контейнеров большинство самых быстрых алгоритмов сортировки нестабильны, поэтому стандарт включает в себя как std::sort (быстрый, но не обязательно стабильный), так и std::stable_sort (стабильный, но часто несколько медленный) .

Однако оба из них, как правило, ожидают итераторы с произвольным доступом и будут плохо работать (если вообще будут) с чем-то вроде связанного списка. Чтобы получить достойную производительность для связанных списков, стандарт включает list::sort. Однако для связанного списка такого компромисса на самом деле не существует - довольно просто реализовать сортировку слиянием, которая одновременно стабильна и (примерно) так же быстро, как и все остальное. Поэтому им просто требовалась одна sort функция-член, которая должна быть стабильной.

Answer 2

Это полностью определенная реализация. Единственное, что говорит стандарт об этом, это то, что его сложность - O (n lg n), и что сортировка stable . То есть относительный порядок равных элементов гарантированно не изменится после сортировки.

Функция сортировки

std::list обычно реализуется с использованием некоторой формы сортировки слиянием, потому что сортировка слиянием стабильна, а слияния действительно очень дешевы при работе со связанными списками.

Надеюсь, это поможет:)

Answer 3

Хотя это зависит от реализации / поставщика, но большинство известных мне реализаций использует Introsort, сложность которого в худшем и худшем случае равна O (nlogn).

Справка: http://en.wikipedia.org/wiki/Introsort