Да, это намеренно. Хотя Big-O слияния меньше, чем у квадратичных сортировок, таких как сортировка вставкой, выполняемые операции более сложны и, следовательно, медленнее.
Рассмотрим сортировку массива длиной 8. Сортировка слиянием делает ~ 14 рекурсивных вызовов сама себе в дополнение к 7 операциям слияния. Каждый рекурсивный вызов вносит некоторые нетривиальные издержки во время выполнения. Каждая операция слияния включает цикл, в котором индексные переменные должны быть инициализированы, увеличены и сравнены, временные массивы должны быть скопированы и т. Д. В целом можно ожидать более 300 «простых» операций.
С другой стороны, сортировка вставок по своей природе проста и использует около 8 ^ 2 = 64 операций, что намного быстрее.
Думайте об этом так. Когда вы сортируете список из 10 чисел вручную, вы используете сортировку слиянием? Нет, потому что ваш мозг гораздо лучше справляется с такими простыми вещами, как вставка. Однако, если бы я дал вам год, чтобы отсортировать список из 100 000 чисел, вы, возможно, были бы более склонны к сортировке списка.
Что касается магического числа 7, оно эмпирически выведено как оптимальное.
РЕДАКТИРОВАТЬ: В стандартном виде вставки из 8 элементов в худшем случае получается ~ 36 сравнений. В канонической сортировке слиянием у вас есть ~ 24 сравнения. Добавление накладных расходов от вызовов методов и сложности операций, сортировка вставки должна быть быстрее. Кроме того, если вы посмотрите на средний случай, сортировка вставки будет производить гораздо меньше сравнений, чем 36.