Очевидно, «потому что это быстрее для небольших массивов».
Основная причина, почему это быстрее, состоит в том, что в процессоре есть огромные штрафы за выбор, на который процессор не может предсказать ответ.Это так называемые трубопроводные киоски.Сортировка вставок сводит к минимуму задержки конвейера.
У эффективных сортировок есть много вопросов или вопросов, у которых даже есть шансы оказаться в любом случае.Так, например, половина сравнений в быстрой сортировке будет предсказана неправильно.Так, например, с 100 элементами мы ожидаем, что потребуется около 650 сравнений (на самом деле в среднем 647,85 см. Стр. 12 из http://ac.informatik.uni -freiburg.de / lak_teaching / ws08_09 / average-case / average_case.pdf для формулы) которой в среднем половина предсказывается неправильно для 325 конвейерных остановок.
У сортировки вставок есть много предсказаний, но их результат очень предсказуем - мы еще не достигли точки вставки.Таким образом, из 100 элементов мы в среднем получим около 2500 сравнений, но только 99 из них будут конвейерными.Если остановка конвейера стоит намного больше 10 сравнений, это ускорит сортировку вставок.По https://gist.github.com/jboner/2841832 вы можете видеть, что захват числа для сравнения составляет около 0,5 нс, а ошибочный прогноз ветвления (то есть остановка конвейера) составляет около 5 нс, поэтому разница составляет около 10 раз. Именно поэтому 100 элементовнаходится примерно в точке, где сортировка вставкой становится быстрее, чем быстрая сортировка на практике.
Пузырьковая сортировка не справляется с этой метрикой.У нас обоих есть квадратичное число сравнений и квадратичное число остановок конвейера.Но это не должно быть сюрпризом.Основная цель сортировки по пузырькам - сделать удобную боксерскую грушу, потому что ее легко кодировать и так плохо сосать.