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

Ответ 1

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

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

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

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

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

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

Ответ 2

Я не знаю о документации, но реализация 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 (элементов объекта) за кулисами. Эта реализация использует сортировку слияния или сортировку по типу.

Ответ 3

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

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

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

Ответ 4

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

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

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

Коллекции. Сортируйте делегаты в Array.sort, поэтому вы видите javadoc, ссылающийся на MergeSort.

Ответ 5

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

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

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

Стабильность - это большое дело при сортировке произвольных объектов. Это приятное побочное преимущество, которое Merge Sort гарантирует n log n (время), независимо от того, какой вход. Для этого сортировка сортировки выбирается для обеспечения стабильной сортировки (Сортировка Merge) для сортировки ссылок на объекты.