Почему Java 6 Arrays # sort (Object []) изменяется от mergesort до insertionsort для небольших массивов?

Java 6 mergesort-реализация в Arrays.java использует сортировку вставки, если длина массива меньше некоторого порогового значения. Это значение жестко закодировано до 7. Поскольку алгоритм является рекурсивным, это в конечном итоге происходит много раз для большого массива. Канонический алгоритм сортировки слияния не делает этого, просто используя merge-sort до конца, пока в списке не останется только 1 элемент.

Это оптимизация? Если да, то как это должно помочь? И почему 7? Сортировка вставки (даже из <=7 вещей) увеличивает количество сравнений, необходимых для сортировки большого массива, - так что добавит стоимость в сортировку, где compareTo() вызовы будут медленными.

(ось x size of array, ось y # of comparisons для разных значений INSERTIONSORT_THRESHOLD)

Ответ 1

Да, это намеренно. В то время как Big-O of mergesort меньше, чем у квадратичных сортировок, таких как сортировка вставки, операции, которые он выполняет, более сложны и, следовательно, медленнее.

Рассмотрим сортировку массива длины 8. Сортировка слияния делает ~ 14 рекурсивных вызовов для себя в дополнение к 7 слияниям. Каждый рекурсивный вызов вносит некоторые нетривиальные накладные расходы во время выполнения. Каждая операция слияния включает цикл, в котором индексные переменные должны быть инициализированы, увеличены и сопоставлены, временные массивы должны быть скопированы и т.д. В целом вы можете ожидать более 300 "простых" операций.

С другой стороны, сортировка вставки по сути проста и использует около 8 ^ 2 = 64 операций, которые намного быстрее.

Подумайте об этом так. Когда вы сортируете список из 10 номеров вручную, вы используете сортировку слияния? Нет, потому что ваш мозг намного лучше делает простые вещи, такие как сортировка вставки. Однако, если я даю вам год для сортировки списка из 100 000 номеров, вы можете быть более склонны к его сортировке.

Что касается магического числа 7, то эмпирически получается оптимальным.

РЕДАКТИРОВАНИЕ: В стандартном вставке из 8 элементов сценарий наихудшего случая приводит к ~ 36 сравнениям. В каноническом слиянии вы имеете ~ 24 сравнения. При добавлении служебных данных из вызовов метода и сложности операций сортировка вставки должна быть быстрее. Кроме того, если вы посмотрите на средний случай, сортировка вставки будет намного меньше сравнений, чем 36.

Ответ 2

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

Ответ 3

Сортировка вставки - это n (n-1)/2, а сортировка слияния - n * (log n с базой 2).

Учитывая это -

Для массива длины 5 = > Сортировка вставки = 10 и сортировка слияния 11.609
Для массива длины 6 = > Сортировка вставки = 15 и сортировка слияния - 15.509
Для массива длины 7 = > Сортировка вставки = 21 и сортировка слияния - 19.651
Для массива длины 8 = > Сортировка вставки = 28 и сортировка слияния 24

Из приведенных выше данных ясно, что до длины 6 сортировка вставки быстрее, а после 7 - сортировка слияния.

Это объясняет, почему используется 7.