Метод вставки

Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1],R[2],...,R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место. Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность
нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. На j - м шаге К[j] сравнивается по очереди сK[j-1],K[j-2],...(K[1]<=K[2]<=...<=K[j-1]) до тех пор, пока выполняется условие K[j]<K[i] (i=j-1,j-2,...) или достигнут левый конец упорядоченной подтаблицы (i=1, K[j]<K[1]). Выполнение условия K[j]>=K[i] означает, что запись R[j] нужно вставить между R[i] и R[i+1]. Тогда записи R[i+1], R[i+2],...,R[j-1] сдвигаются на одну позицию, и запись R[j] помещается в позицию i+1.
Операции сравнения и перемещения записей удобно совмещать,перемежая их друг с другом (этот способ называется "просеиванием").
Ниже показано выполнение j-го шага сортировки ( с "просеиванием" ).

5 8 10 14 6 2 11 ¦ j=5, i=4, 6 < 14
<-~~ ¦
5 8 10 6 14 2 11 ¦ i=3, 6 < 10
<-~~ ¦
5 8 6 10 14 2 11 ¦ i=2, 6 < 8
<-~~ ¦
5 6 8 10 14 2 11 ¦ i=1, 6 > 5

Количество операций сравнения для метода вставки определяется по формуле

n * (n - 1)
C = ------------
4
При достаточно большом числе элементов в сортируемой таблице можно принять C = n**2/4 . Максимальное количество перестановок при использовании этого метода примерно равно n**2/4
Метод вставки обычно используется тогда, когда записи вносятся в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушалась.

Модифицированный метод вставки ( бинарное включение )

Метод прямого включения можно улучшить,если вставлять очередной элемент таблицы в упорядоченную подтаблицу с помощью метода бинарного (дихотомического,двоичного,логарифмического) поиска.
j-й шаг сортировки:

5 6 8 10 14 18 9 2 ¦ i = 6/2 = 3; 9 > 8
~~~~~~ ~~~~~~~~~ ~~ ¦
отбрасывается рассматривается ¦
--¬ ¦
. . . 10 14 18 9 2 ¦ i = (4+6)/2 = 5;
~~ ~~~~~ ¦ 9 < 14
рассм. отбрас. ¦
¦
. . . 9 10 14 18 2 ¦ i = 4; 9 < 10