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

Ответ 1

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

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

Здесь цитата:

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

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

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

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

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

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

Связанные вопросы

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

Численный пример

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

• 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.

Ответ 2

Это для скорости. Накладные расходы на mergeSort достаточно высоки, что для коротких массивов он будет медленнее, чем сортировка вставки.

Ответ 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.

Ответ 4

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