Сортировка вставок - хороший выбор для «небольших» наборов данных.Что такое "маленький"?

Question

Я видел много мест, где говорится о том, как сортировка вставкой хороша для небольших наборов данных.Я не могу найти номер для того, что "маленький", хотя.Я предполагаю, что нет абсолютного ответа и что это зависит от типа машины, на которой выполняется код.

Однако, какие факторы влияют на определение порогового значения, когда сортировка вставкой является хорошей идеей?А какие приблизительные цифры для "маленьких"?5?10?50?100?

Спасибо!

Сайт, который говорит, что Сортировка вставок подходит для небольших наборов данных: https://www.toptal.com/developers/sorting-algorithms/insertion-sort

Answer 1

Да, ваша догадка верна - нет абсолютного ответа, нужно измерить, где находится порог между сортировкой вставок и другими методами.

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

Answer 2

Попытка ответа, если мы говорим об общей проблеме сортировки.Сортировка вставки в среднем O (n ^ 2), эффективные алгоритмы сортировки в среднем O (nlogn).Так смутно говоря, если что-то предпринимает K шагов для эффективной сортировки, это займет около (вроде) K ^ 2 шагов с сортировкой вставкой.

Так что, если n> K слишком медленное для вас по вкусу с эффективной сортировкой, n> K ^ 0.5 будет слишком медленным для вас (грубо) с сортировкой вставкой.

Практически говоря, скажем таквы можете сортировать массивы размером 10 ^ 8 с помощью чего-то более эффективного, тогда вы можете с радостью сортировать массивы размером 10 ^ 4 с помощью сортировки вставкой.