std :: sort() использует Introsort algorithm, который переключается между быстрым сортировкой кучи & в зависимости от текущего коэффициента сортировки.STL Сортировка против медианы медианов
Есть ли практический недостаток для внедрения медиа-посредников Quicksort вместо Introsort? В конце концов, сложнее моделировать смесь алгоритмов сортировки теоретически & вычислить их худшую сложность случая - хотя я предполагаю, что Introsort будет O (N log N).
См. Оригинал оригинала Муссера на Introsort. В принципе, хотя медиана медиан и Introsort одинаково асимптотически, Introsort делает менее постоянную работу за элемент и, как правило, быстрее. В документе упоминается, что медиана медиан будет в порядке, чем резервная сортировка, а не куча сортировки.
David R. Musser. Интроспективные алгоритмы сортировки и выбора. [Postscript version]
Из того, что я помню, Quicksort плохо работает с сортированными или очень сортированными коллекциями - O (n^2). Посмотрите страницу Википедии на Introsort - с убедительной статистикой на Introsort против Quicksort.
Медиана версии мерседесов в худшем случае O (n log n) и является наихудшим оптимальным вариантом – PKG
Мой плохой - я не знал об этом, спасибо user356106. Я предполагаю, что реализую медианы медианов и смотрю, как это происходит против интросорта для окончательного ответа. –
не уверен, что ваш вопрос здесь? –
Может ли кто-нибудь объяснить, почему? Вопрос должен быть ясен: есть ли практический недостаток для внедрения медиа-посредников Quicksort вместо Introsort? И кто-то уже дал ответ. – PKG