Сортировка вставками

Берём исходные элементы и складываем в результат в отсортированном порядке. Для каждого нового элемента в результате находим правильное место и вставляем, раздвигая результат.

Сортировать будем начало массива, текущий элемент будем менять местами с предыдущим, пока он не займет правильного места. Так мы одновременно реализуем и поиск нужной позиции, и вставку.

procedure InsertionSort(var A: TAI);
var
    i, j: integer;
begin
  for i := Low(A)+1 to High(A) do
  begin
    j := i;
    while (j > Low(A)) and (A[j] < A[j-1]) do
    begin
      swap(A[j], A[j-1]);
      dec(j);
    end;
  end;
end;

Сложность: