Почему Collections.sort использует Mergesort, а Arrays.sort - нет?

Я использую JDK-8 (x64). Для Arrays.sort(примитивов) я нашел в документации по Java следующее:

Алгоритм сортировки - это Dual-Pivot Quicksort от Владимира Ярославского, Джона Бентли и Джошуа Блоха.

Для Collections.sort(объектов) я нашел этот "Тимсорт":

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

Если Collections.sortиспользуется массив, почему он просто не вызывает Arrays.sortили не использует QuickSort с двумя поворотами ? Зачем использовать Mergesort ?

API гарантирует стабильную сортировку, чего не предлагает Quicksort . Однако при сортировке примитивных значений по их естественному порядку вы не заметите разницы, поскольку примитивные значения не имеют идентичности. Следовательно, быстрая сортировка может использоваться для примитивных массивов и будет использоваться, когда будет сочтена более эффективной¹.

Для объектов вы можете заметить, когда объекты с разными идентификаторами, которые считаются равными в зависимости от их equalsреализации или предоставленного, Comparatorизменяют свой порядок. Таким образом, Quicksort не вариант. Таким образом, используется вариант MergeSort , текущие версии Java используют TimSort . Это применимо к обоим, Arrays.sortи Collections.sort, хотя в Java 8, Listсам по себе может переопределить алгоритмы сортировки.

¹ Преимущество быстрой сортировки в эффективности заключается в том, что при выполнении на месте требуется меньше памяти. Но он имеет потрясающую производительность в худшем случае и не может использовать прогоны предварительно отсортированных данных в массиве, что делает TimSort .

Поэтому алгоритмы сортировки переделывались от версии к версии, оставаясь при этом в классе, который теперь неправильно назван DualPivotQuicksort. Кроме того, документация не обновилась, что показывает, что в целом плохая идея - указывать в спецификации внутренний алгоритм, когда в этом нет необходимости.

Текущая ситуация (включая Java 8 - Java 11) выглядит следующим образом:

• Как правило, методы сортировки примитивных массивов используют быструю сортировку только при определенных обстоятельствах. Для больших массивов они сначала попытаются идентифицировать прогоны предварительно отсортированных данных, как это делает TimSort , и объединят их, когда количество прогонов не превысит определенный порог. В противном случае они вернутся к быстрой сортировке , но с реализацией, которая вернется к сортировке вставкой для небольших диапазонов, что не только влияет на небольшие массивы, но и на рекурсию быстрой сортировки.
• sort(char[],…)и sort(short[],…)добавьте еще один особый случай, чтобы использовать сортировку с подсчетом для массивов, длина которых превышает определенный порог
• Точно так же sort(byte[],…)будет использоваться сортировка подсчетом , но с гораздо меньшим порогом, что создает самый большой контраст с документацией, поскольку sort(byte[],…)никогда не использует быструю сортировку. Он использует только сортировку вставкой для небольших массивов и сортировку подсчетом в противном случае.

Я не знаю о документации, но реализация java.util.Collections#sortв Java 8 (HotSpot) выглядит следующим образом:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

И List#sortимеет эту реализацию:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Итак, в конце концов, Collections#sortиспользует Arrays#sort(элементов объекта) за кадром. В этой реализации используется сортировка слиянием или сортировка по времени.

Согласно Javadoc, только примитивные массивы сортируются с использованием Quicksort. Массивы объектов также сортируются с помощью сортировки слиянием.

Итак, Collections.sort, похоже, использует тот же алгоритм сортировки, что и Arrays.sort для объектов.

Другой вопрос, почему для примитивных массивов используется другой алгоритм сортировки, чем для массивов объектов?

Как указано во многих ответах.

Быстрая сортировка используется Arrays.sort для сортировки примитивных коллекций, потому что стабильность не требуется (вы не будете знать и не заботитесь, были ли поменяны местами два идентичных целых числа при сортировке)

MergeSort или, более конкретно, Timsort используется Arrays.sort для сортировки коллекций объектов. Требуется стабильность. Quicksort не обеспечивает стабильности, Timsort обеспечивает.

Collections.sort делегирует Arrays.sort, поэтому вы видите javadoc, ссылающийся на MergeSort.

Быстрая сортировка имеет два основных недостатка, когда дело доходит до сортировки слиянием:

• Это нестабильно, когда дело касается непримитивности.
• Это не гарантирует производительности n log n.

Стабильность не является проблемой для примитивных типов, поскольку нет понятия идентичности, отличного от (значения) равенства.

Стабильность очень важна при сортировке произвольных объектов. Хорошим дополнительным преимуществом является то, что сортировка слиянием гарантирует производительность n log n (время) независимо от входных данных. Вот почему выбрана сортировка слиянием, чтобы обеспечить стабильную сортировку (сортировку слиянием) для сортировки ссылок на объекты.