#sorting #quicksort #mergesort #timsort
#сортировка #быстрая сортировка #сортировка слиянием #timsort
Вопрос:
Недавно я наткнулся на шаблон, побеждающий быструю сортировку (pdqsort). https://github.com/orlp/pdqsort
https://github.com/stjepang/pdqsort
Тем не менее, я не смог найти какое-либо обширное исследование, которое описывает pdqsort и сравнивает его с другим популярным Timsort. Кто-нибудь знает, как эти 2 алгоритма работают друг против друга? Есть ли где-нибудь бумага? Спасибо.
Комментарии:
1. Из первой ссылки уже есть контрольные данные. std::stable_sort выполняется быстрее в двух случаях: «pipe organ» и «push front». В X86-X64 в 64-разрядном режиме с 16 регистрами я нахожу, что сортировка слиянием в 4 способа без кучи выполняется так же быстро или немного быстрее, чем минимальная быстрая сортировка, без возврата к кучной сортировке со случайными данными.