Как правило, гибридная сортировка слиянием снизу вверх / вставка сортировки выбирает размер группы от 16 до 128 элементов, так что сортировка слиянием делает четное число проходов, так что данные попадают обратно в исходный массив (так как они сортировки слиянием обычно меняют направление слияния между исходным и рабочим массивом на каждом проходе слияния). Для степени сортировки вставок нет ничего особенного в степени 2, поэтому можно использовать любой разумный размер для групп сортировки вставок.
Я не исследовал алгоритмы выбора «идеального» размера группы. Грубый подход заключается в определении количества проходов для «чистой» сортировки слиянием ceil (log2 (n)), а если число проходов нечетное, используйте 32 или 128 для размера группы и, если четное, используйте 64 для размера группы. Рассмотрим случай, когда n = 8000000. Число проходов для чистой сортировки слиянием равно 23, поэтому выберите 32 или 128 для размера группы, сократив число проходов до 18. Для попытки улучшенного выбора (оказывается, это не улучшение), если число проходов будет нечетным, используйте количество групп от 17 до 32 или от 65 до 128, а если число проходов четное, используйте количество групп от 33 до 64. Рассмотрим случаи где n = 1 + некоторая степень 2. Для n = 1 + 2 ^ 22 = 4194305 число проходов равно 23, а при использовании размера группы 32 это уменьшается до 18 проходит, а 128 уменьшает его до 16 проходов. Затем вычислите ceil (n / (2 ^ 18)) = 17 или ceil (n / (2 ^ 16)) = 65.
С тех пор я тестировал, используя 17, 32 или 65 для n = 1 + 2 ^ 22 = 4194305 с кодом C ++ (Visual Studio 2015, 64-разрядная версия Win 7 Pro), и это не имело практически никакого значения, изменение было в пределах варианта, который я получаю от повторных прогонов с тем же кодом (отклонение менее 1,5%).