Удивительная история развития сортировки в JDK
Как вы считаете, если выполнить java.util.Arrays.sort() , то какая сортировка будет вызвана? Quicksort? Timsort? И та, и другая, потому что для объектов вызывается Timsort , а для примитивов (чисел int, long, float и так далее) — Dual-Pivot Quicksort . В JDK 6 для объектов использовался стандартный Merge sort , а для чисел классическая реализация Quicksort с одним опорным элементом, предложенная Джоном Бентли и Дугласом МакИлрой. В JDK 7 оба алгоритма поменялись: теперь объекты сортируются с помощью Timsort , автор Тим Петерс, а для простых типов данных используется Dual-Pivot Quicksort , предложенный мною вместе с Джоном Бентли и Джошем Блоком в 2009 году. Эта сортировка используется более 15 лет не только в JDK, но и в Android (хотя и немного устаревшая версия). А зачем нам вообще второй алгоритм сортировки, если есть Timsort? Почему не использовать один и для объектов, и для примитивов? Сегодня я, как автор, расскажу историю Dual-Pivot Quicksort: как он начинался, как развивался и как продолжает развиваться сейчас.
https://habr.com/ru/companies/sberbank/articles/841342/