Сортировка простым вставками (с бинарным поиском) :: Insertion Sort (binary search)

Оптимизация для сортировки простыми вставками

Оптимизация

Место для вставки производится с помощью бинарного поиска.

Оптимизация не даёт принципиального приращения скорости, поскольку поиск места для вставки не является критичным для временной сложности алгоритма.

Характеристики алгоритма

НазваниеСортировка простыми вставками с бинарным поиском (Insertion Sort (binary search))
КлассСортировки вставками
УстойчивостьДа
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 4)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки вставками

Сортировка вставками

Insertion sort

Реализация на различных ЯП