Изменения

=== Бинарные вставки ===

Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно количество сравнений изменится с <tex>O(N^2)</tex> до <tex> O(N\log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить элемент на на своё место, всё ещё необходимо переместить большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось. Бинарные вставки выгодно использовать только в случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел.

'''for''' i = 1 '''to''' n - 1

j = i - 1

'''for''' m = j '''downto''' k

swap(a[m], a[m+1])

=== Двухпутевые вставки ===

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается путём сдвига элементов влево или вправо туда, куда выгоднее.