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

Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом:

исходное положение: d c a b;

первый проход: c d a b;

второй проход: a c d b;

третий проход: a b c d.

Ниже приводится алгоритм сортировки вставкой:

{ сортировка вставкой }

procedure Inser(var item: DataArray; count:integer);

var

i, l: integer;

x: DataItem;

begin

for i := 2 to count do

begin

x := item[i];

j := i-1;

while (x<item[j]) and (j>0) do

begin

item[j+1] := item[j];

j := j-1;

end;

item[j+1] := x;

end;

end; { конец сортировки вставкой }

В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1.

Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n2 +n)-1,давая в среднем значение 1/4 (n2+n-2).

Число операций обмена будет следующим:

для лучшего случая: 2 (n-1);

в среднем: 1/4 (n2+9n-10);

для худшего случая: 1/2 (n2+3n-4).

Таким образом, число операций обмена для худшего случая будет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т.е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам.

Несмотря на то, что число сравнений может быть довольно небольшим для определенных наборов данных, постоянные сдвиги массива требуют выполнения большого числа операций пересылок.

Однако, сортировка вставкой имеет естественное поведение, требуя наименьшее число операций обмена для почти упорядоченного списка и наибольшее число операций обмена, когда массив упорядочен в обратном направлении.