Реализация Arrays.sort, что он делает конкретно

Question

Какой алгоритм сортировки использует Arrays.sort в Java? Динамически изменяется ли она в зависимости от операционной системы, размера ввода или чего-то еще?

Answer 1

Вы можете видеть из источника, что он делает на OpenJDK. Для примитивных типов он использует сортировку вставки для коротких массивов и модифицированную quicksort для более длинных; и сортировка по типу для массивов объектов.

Java 6 Arrays.sort()

Я не вижу, как операционная система будет производить сортировку.

Answer 2

Посмотрите на документации для Arrays.sort: записка

реализации: Эта реализация является устойчивым, адаптивной, итерационным слиянием, что требует гораздо меньше, чем п Л.Г. (п) сравнения , когда массив входа частично отсортированный, предлагая производительность традиционного объединения, когда входной массив случайным образом упорядочен. Если входной массив почти отсортирован, реализация требует приблизительно n сравнений. Временное хранение требования варьируются от небольшой константы для почти отсортированных входных массивов до n/2 ссылок на объекты для произвольно упорядоченных массивов ввода.

Реализация принимает одинаковое преимущество по возрастанию и убыванию в своем массиве ввода и может использовать по возрастанию и по убыванию в разных частях одного и того же входного массива. Это , хорошо подходящий для слияния двух или более отсортированных массивов: просто объедините массивы и отсортируйте полученный массив.

Реализация была адаптирована для сортировки списка Тима Петерса для Python (TimSort). Он использует из Питера Методики Макилрой «Оптимистической Сортировкой и информацией Теоретико сложности», Труды четвертой ежегодной ACM-SIAM симпозиума по дискретным алгоритмам, С. 467-474, января 1993

Посмотри на исходный код: Arrays.sort.

Answer 3

sort метод перегружен.

Для Java 7 рассмотрите примечания по реализации для разных типов, начиная с here и далее вниз.