Сортировка простым вставками (с бинарным поиском) :: Insertion Sort (binary search)
Оптимизация для сортировки простыми вставками
Оптимизация
Место для вставки производится с помощью бинарного поиска.
Оптимизация не даёт принципиального приращения скорости, поскольку поиск места для вставки не является критичным для временной сложности алгоритма.
Характеристики алгоритма
| Название | Сортировка простыми вставками с бинарным поиском (Insertion Sort (binary search)) | |
|---|---|---|
| Класс | Сортировки вставками | |
| Устойчивость | Да | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2 / 2) |
| Средняя | O(n2 / 4) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Сортировка вставками
Реализация на различных ЯП