В чем разница между быстрой сортировкой с двойным поворотом и быстрой сортировкой?

Я нахожу это в документе Java.

Алгоритм сортировки — это Dual-Pivot Quicksort Владимира Ярославского, Джона Бентли и Джошуа Блоха. Этот алгоритм обеспечивает производительность O(n log(n)) для многих наборов данных, из-за которой производительность других методов быстрой сортировки снижается до квадратичной, и обычно он быстрее, чем традиционные реализации быстрой сортировки (с одним поворотом).

Затем я нахожу это в результатах поиска Google. Теория алгоритма быстрой сортировки:

1. Выберите из массива элемент, называемый сводной точкой.
2. Переупорядочите массив так, чтобы все элементы, которые меньше опорного, располагались перед опорным, а все элементы, превышающие опорный, шли после него (равные значения могут идти в любом случае). После этого разделения поворотный элемент находится в своем конечном положении.
3. Рекурсивно отсортируйте подмассив меньших элементов и подмассив больших элементов.

Для сравнения, быстрая сортировка с двумя сводами:

()

1. Для небольших массивов (длина ‹ 17) используйте алгоритм сортировки вставками.
2. Выберите два опорных элемента P1 и P2. Мы можем получить, например, первый элемент a[left] как P1, а последний элемент a[right] как P2.
3. P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
   • part I with indices from left+1 to L–1 with elements, which are less than P1,
   • часть II с индексами от L до K–1 с элементами, которые больше или равны P1 и меньше или равны P2,
   • часть III с индексами от G+1 до right–1 с элементами больше P2,
   • часть IV содержит остальные элементы, подлежащие рассмотрению, с индексами от K до G.
4. Следующий элемент a[K] из части IV сравнивается с двумя опорными точками P1 и P2 и помещается в соответствующую часть I, II или III.
5. Стрелки L, K и G изменяются в соответствующих направлениях.
6. Шаги 4-5 повторяются, пока K ≤ G.
7. Поворотный элемент P1 заменяется последним элементом из части I, поворотный элемент P2 заменяется первым элементом из части III.
8. Шаги 1–7 рекурсивно повторяются для каждой части I, части II и части III.

Я просто хочу добавить, что с точки зрения алгоритма (т.е. стоимость учитывает только количество сравнений и перестановок), быстрая сортировка с 2 точками и 3 точками не лучше, чем классическая быстрая сортировка (которая использует 1 точку), если не худший. Однако на практике они работают быстрее, поскольку используют преимущества современной компьютерной архитектуры. В частности, их количество промахов кеша меньше. Так что если убрать все кеши и оставить только ЦП и оперативную память, то в моем понимании 2/3-опорная быстрая сортировка хуже классической быстрой сортировки.

Ссылки: быстрая сортировка по трем точкам: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 Анализ того, почему они работают лучше классической быстрой сортировки: https://arxiv.org/pdf/1412.0193v1.pdf Полный и не слишком подробный справочник: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf

Кому интересно, посмотрите, как они реализовали этот алгоритм на Java:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%2Cint%5B%5D%2Cint%2Cint%29

Как указано в источнике:

"Сортирует указанный диапазон массива, используя заданный фрагмент массива рабочей области, если это возможно для слияния

Алгоритм предлагает производительность O(n log(n)) для многих наборов данных, из-за которой другие быстрые сортировки ухудшаются до квадратичной производительности, и, как правило, быстрее, чем традиционные (с одним поворотом) реализации быстрой сортировки».