Идея метода сходна с сортировкой прямыми включениями.Часть последовательности до испытуемого (i-ого) элемента ("готовая" часть) делится пополам и i-ый элемент сравнивается с элементом, стоящим на середине, после чего границы поиска уменьшаются в два раза. Получившийся полуинтервал делится пополам, и процесс повторяется до тех пор, пока не будет определено место включения i-ого элемента. Затем происходит сдвиг вправо на одну позицию тех элементов, которые расположены от места включения до i-ого элемента, освобождая таким образом позицию для i-ого элемента.
Текстовый алгоритм:
1.Начало.
2.Выполнить цикл, пока имеет значение от 2 до с шагом = 1
а) X = A(i), l = 1, r = i-1
б) Если l > r, то:
1) выполнить цикл, пока j имеет значение от (i-1) до l с шагом = -1
телоцикла: A(j + 1) = A(j)
2) присвоить A(l) = Xиначе:
1) присвоить m = (l + r) \ 2
2) если X<A(m), то r = m – 1 иначе l = m + 1
3) перейти к пункту б). 3.Конец.