Да!... а также номер.
Сводка
В текущих реализациях Open JDK 0 Тим Сорт обычно используется для сортировки массивов объектов (т. е. Arrays.sort(Object[]) и друзья) - но для примитивных массивов (остаток от Arrays.sort методов) используется множество других методов.
Для примитивов используется эвристикаВыберите среди разновидностей методов сортировки, таких как быстрая сортировка, сортировка слиянием, сортировка с подсчетом 3 .в зависимости от сортируемых данных.Большинство из этих решений просто принимаются заранее, основываясь на типе и размере сортируемого массива, но для элементов int и long решение фактически адаптивное на основе измеренной сортировки массива.Таким образом, у вас есть адаптация / самоанализ (эвристика выбора алгоритма) поверх адаптации / самоанализа (TimSort или подобная сортировка слиянием) во многих случаях!
Подробно
Тим Сорт используется для большинствавиды объектов, такие как Arrays.sort(Object[] a), если пользователь специально не запросил устаревшее поведение, установив системное свойство java.util.Arrays.useLegacyMergeSort в значение true.
Для примитивов ситуация более сложная.По крайней мере, начиная с JDK 8 (версия 1.8.0_111) используются различные эвристики в зависимости от размера сортируемых массивов, типа примитива и измеренной «сортировки» массива.Вот краткий обзор:
- Для всех типов примитивов, кроме байтов 1 , массивы менее 47 элементов просто сортируются с использованием сортировки вставкой (см.
DualPivotQuicksort.INSERTION_SORT_THRESHOLD).Этот порог также используется при сортировке подмассивов, которые возникают при использовании слияния или быстрой сортировки, а размер подмассива падает ниже порога.Таким образом, некоторая форма сортировки вставок будет использоваться во всех видах, и для небольших массивов это единственный используемый алгоритм. - Для примитивных типов
byte, short и char, подсчет sort используется для больших массивов.Это простая сортировка, которая занимает O(n + range) времени, где range - общее количество значений в байтах (256) или short / char (65536).Сортировка включает в себя выделение базового массива range значений, поэтому он используется только тогда, когда количество элементов для сортировки составляет значительную часть общего диапазона.В частности, он используется для байтовых массивов, превышающих 29 элементов (т. Е. ~ 11% диапазона), и коротких / символьных массивов, превышающих 3200 элементов (~ 5% диапазона). - Для байтовых массивоввсегда используется один из двух вышеуказанных подходов.
- Для массивов
int и long выше порога сортировки вставки и для массивов short / char как выше порога сортировки вставки, так и нижеСчитая порог сортировки, можно использовать один из двух алгоритмов: быстрая сортировка с двойным поворотом или сортировка слиянием.Какой из них использовать, зависит от меры сортировки массива: вход делится на пробегов восходящих или нисходящих элементов.Если число таких запусков больше 66, то массив считается в основном несортированным и сортируется с помощью быстрой сортировки с двумя поворотными точками.В противном случае массив считается в основном отсортированным, и используется сортировка слиянием (с использованием уже перечисленных прогонов в качестве отправной точки).
идея для поиска прогонов и затем с использованием сортировки слиянием дляСортировка их на самом деле очень похожа на TimSort, хотя есть некоторые различия.Поэтому, по крайней мере, для некоторых параметров JDK использует сортировку с учетом запусков, но для многих других комбинаций параметров он использует другой алгоритм, и всего используется не менее 5 различных алгоритмов!
Обоснование
Причины различного поведения сортировки Object[] по сравнению с примитивом, вероятно, по крайней мере двоякие:
1) Сорта Object[] должны быть стабильными : объекты, которые сортируются одинаково, будут отображаться в том же порядке, что и входные данные. Для примитивных массивов такого понятия не существует: примитивы полностью определяются по их значению, поэтому нет различия между стабильным и нестабильным типом. Это позволяет примитивным видам обходиться без необходимости стабильных алгоритмов в пользу скорости.
2) Виды Object[] должны включать метод Object.compare(), который может быть сколь угодно сложным и дорогим. Даже если метод compare() прост, как правило, накладные расходы будут вызываться только в том случае, если весь метод сортировки может быть встроен 2 . Так что сорта Object[], как правило, будут смещены в сторону минимизации общего сравнения даже ценой некоторой дополнительной алгоритмической сложности.
Виды примитивных массивов, с другой стороны, просто напрямую сравнивают примитивные значения, которые обычно принимают порядок цикла или двух. В этом случае алгоритм должен быть оптимизирован с учетом как стоимости сравнений, так и окружающего алгоритма, поскольку они могут иметь одинаковую величину.
0 По крайней мере для версий между Java 7 и Java 9, и, конечно, это также включает JDK Oracle, поскольку он основан на Open JDK. вероятно , что другие реализации используют аналогичный подход, но я не проверял.
1 Для байтовых массивов порог сортировки при вставке составляет, по сути, 29 элементов, поскольку это нижний предел, выше которого используется сортировка при подсчете.
2 Это кажется маловероятным, поскольку оно довольно большое.
3 Счетная сортировка используется только для значений с относительно ограниченным диапазоном из 16 бит или менее: byte, short или char.