Изменения

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

|colspan=3|''Первый проход (проталкиваем второй первый элемент — '''''5''''')''

|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов , то мы просто добавляем элемент туда.

|colspan=3|''Второй проход (проталкиваем третий второй элемент — '''''7''''')''

|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.

|colspan=3|''Третий проход (проталкиваем четвертый третий — '''''3''''')''

|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и , так как позиция крайняя , то сдвигать ничего не приходится.

|colspan=3|''Четвертый проход (проталкиваем пятый четвертый элемент — '''''4''''')''

|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем , чем до правого то , значит сдвигаем левую часть.