Сортировка парными вставками

Модификация сортировки вставками.

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

type
  TAI = array of integer;
...
procedure PairedInsertionSort(var A: TAI);
var
    i, j: integer;
    buf: integer;

    // Вставка одного элемента.
    function Insertion(Index, aValue, aShift: integer): integer;
    begin
      while (Index >= Low(A)) and (A[Index] > aValue) do
      begin
        A[Index+aShift] := A[Index];
        dec(Index);
      end;
      A[Index+aShift] := aValue;
      result := Index;
    end;

begin
  i := Low(A);
  while i<High(A) do
  begin
    // Обработка пары в зависимости от того,
    //  кто из них больше.
    if A[i] > A[i+1]
      then begin
             buf := A[i+1];
             Insertion(Insertion(i-1, A[i], +2), buf, +1);
           end
      else begin
             buf := A[i];
             Insertion(Insertion(i-1, A[i+1], +2), buf, +1);
           end;

    inc(i, 2);
  end;
  // Если количество элементов нечётно,
  //  обработаем оставшийся.
  if i=High(A) then
    Insertion(i-1, A[i], +1);
end;

Сложность: