Я написал алгоритм быстрой сортировки, в котором есть заглушка сортировки вставки, которая вызывается, если раздел для сортировки имеет N элементов или короче.
Я тестировал на старой машине с Core 2, и в результате была получена такая сортировка один миллион ints занял 140 миллисекунд с чистой быстрой сортировкой и меньше времени для смешанной быстрой сортировки + сортировки вставкой.
Меня удивило то, что размер раздела, на котором я назвал сортировку вставкой, должен был быть достаточно большим, чтобы получить лучший результат ( лучше всего было 114 миллисекунд) - около 70, хотя не было очень большой разницы от 60 до 100. Для более коротких размеров разделов, таких как 10, это было медленнее.
Почему это так? Это типичный, правильный результат?
Есть ли что-то, что будет работать еще быстрее? (Обратите внимание, что std::sort из стандартной библиотеки C ++ занимает в моих тестах 111 мс, лишь чуть-чуть лучше, чем 114 мс.)