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

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

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

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

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

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

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

Сортировка вставками — n(n-1)/2, а сортировка слиянием — n*(log n с основанием 2).

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

1. Для массива длины 5 => сортировка вставками = 10, а сортировка слиянием — 11,609.
2. Для массива длины 6 => сортировка вставками = 15, а сортировка слиянием — 15,509.
3. Для массива длины 7 => сортировка вставками = 21, а сортировка слиянием — 19,651.
4. Для массива длины 8 => сортировка вставкой = 28 и сортировка слиянием 24

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

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

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