Почему java.util.Arrays.sort (Object []) использует 2 вида алгоритмов сортировки?

Question

Я обнаружил, что java.util.Arrays.sort(Object[]) использует 2 вида алгоритмов сортировки (в JDK 1.6).

псевдокод:

if(array.length<7)
   insertionSort(array);
else
   mergeSort(array);

Зачем здесь 2 вида сортировки? для эффективности?

Answer 1

Важно отметить, что алгоритм, который является O(N log N), не всегда быстрее на практике, чем алгоритм O(N^2).Это зависит от констант и диапазона N.(Помните, что асимптотическая запись измеряет относительную скорость роста, а не абсолютную скорость).

Для малых N сортировка вставки фактически превосходит сортировку слиянием.Это также быстрее для почти отсортированных массивов.

Вот цитата :

Хотя это один из элементарных алгоритмов сортировки с O(N^2) в худшем случаевремя сортировки вставкой является предпочтительным алгоритмом, когда данные почти отсортированы (потому что они адаптивные) или когда размер проблемы небольшой (потому что у него низкие накладные расходы).

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

Вот еще одна цитата из Лучший алгоритм сортировки для почти отсортированных списков paper:

прямая сортировка с вставкой лучше всего подходит для небольших или почти отсортированных списков

Это означает, что на практике:

• Какой-то алгоритм A ₁ с более высокой асимптотической верхней границей может быть предпочтительнее, чем другой узелwn алгоритм A ₂ с нижней асимптотической верхней границей
  • Возможно A ₂ слишком сложен для реализации
  • Или, возможно, это не имеет значения в диапазоне N, считаемом
    • См., Например, Алгоритм Копперсмита-Винограда
• Некоторые гибридные алгоритмы могут адаптировать разные алгоритмы в зависимости от размера ввода

Смежные вопросы

• Какой алгоритм сортировки лучше всего подходит для повторной сортировкипочти полностью отсортированный список?
• Есть ли когда-нибудь веская причина использовать сортировку вставкой?

---

Числовой пример

Давайте рассмотрим эти две функции:

• f(x) = 2x^2;эта функция имеет квадратичную скорость роста, то есть "O(N^2)"
• g(x) = 10x;эта функция имеет линейную скорость роста, то есть "O(N)"

Теперь давайте построим две функции вместе:

^{Источник: WolframAlpha: plot 2x^2 and 10x for x from 0 to 10}

Обратите внимание, что между x=0..5, f(x) <= g(x), но для любых больших x, f(x) быстро перерастает g(x).

Аналогично, если A ₁ является квадратичным алгоритмом с низкими издержками, а A ₂ являетсялинейный алгоритм с высокими издержками для меньшего ввода A ₁ может быть быстрее, чем A ₂ .

Таким образом, вы можете, если захотите, создать гибридный алгоритм A ₃ , который просто выбирает один из двух алгоритмов в зависимости от размера входных данных.Стоит ли это усилий или нет, зависит от фактических параметров.

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

Answer 2

Это для скорости. Издержки mergeSort достаточно высоки, поэтому для коротких массивов она будет медленнее, чем сортировка вставкой.

Answer 3

Цитируется из: http://en.wikipedia.org/wiki/Insertion_sort

Some divide-and-conquer algorithms such as quicksort and mergesort sort by 
recursively dividing the list into smaller sublists which are then sorted. 
A useful optimization in practice for these algorithms is to use insertion 
sort for sorting small sublists, where insertion sort outperforms these more 
complex algorithms. The size of list for which insertion sort has the advantage 
varies by environment and implementation, but is typically between eight and 
twenty elements.

Answer 4

Похоже, они считают, что mergeSort(array) медленнее для коротких массивов. Надеюсь, они действительно это проверили.