Сортировка простым включением

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

• прост в реализации;
• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать массив по мере его получения;
• не требует временной памяти, даже под стек.

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

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

program pr33;
const
x: array [1.. 8] of integer = (44, 55,12,42, 94,18,06, 67);
var
l, i, j: integer;
begin { вывод на экран исходного массива x }
for i:= 1 то 8 do write(x[i]:5);
writeln;
for i:=2 to 8
do begin
j:= i-1; l:= x[i];
while (j > 0) and (l < х[i])
do begin { переставить х[j] на место х[j+1]}
x[j+1]:=x[j];
j:=j-1;
end;
x[j+1]:=l
end;
{ вывод на экран отсортированного массива x}
for i:= 1 то 8 do write(x[i]:5);
writeln
end.