Сортировка парными вставками :: Pairwise Insertion Sort

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