Каковы недостатки Dual-Pivot Quicksort?

Question

Я знаю, что у него меньше свопов и он быстрее, чем у классической быстрой сортировки, но я не вижу каких-либо недостатков этого алгоритма.

Answer 1

Быстрая сортировка с двойным поворотом сложнее, чем оригинал. Дополнительный шарнир требует, чтобы эти два шарнира сравнивались и при необходимости менялись местами. В массиве есть дополнительный индекс, дополнительный регистр для перемещения элемента и дополнительный своп в конце.

Answer 2

В общем больше числа шарниров, лучше производительность и снова выбор поворота имеет большое значение для любого алгоритма быстрой сортировки. См .: исследование

Плохо выбранные шарниры для двойного поворота будут работать хуже, чем обычная быстрая сортировка с хорошим стержнем. Выбор центра сильно зависит от набора данных. Опять же, для сложных наборов данных выбор большего количества стержней может стать трудным.