Алгоритм сортировки вставками
и его реализация в Delphi

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

   Псевдокод алгоритма сортировки вставками:

Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
  Цикл для i от min+1 до max
    j=i
    tmp=Ai; //запоминаем значение ещё неотсортированного элемента
    цикл пока (j>min и Aj-1>tmp): //Сравниваем очередной отсортированный элемент, если он больше,
      1. Aj=Aj-1 //то сдвигаем его в большую сторону, освобождая место для вставки
      2. j=j-1 //Переходим к следующему элементу в отсортированной части массива
    Aj=tmp; //Место для нового элемента определено - вставляем его туда
Конец процедуры

   Реализация алгоритма сортировки вставками в Delphi:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure injection(var A: TArray; min, max: Integer);
var i, j, tmp: Integer;
begin
for i:=min+1 to max do
  begin
    j:=i;
    tmp:=A[i];
    while ((j>min)and(A[j-1]>tmp)) do
      begin
        A[j]:=A[j-1];
        j:=j-1;
      end;
    A[j]:=tmp;
  end;
end;

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

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

   Таким образом, для массива в 100 000 элементов требуется максимально не 100 000, а не более 18 (100 000 < 2¹⁸) сравнений для нахождения места вставки, для массива из миллиона элементов - не более 21. Правда, дополнительные затраты времени нужны для организации цикла сдвига.Тем не менее, время сортировки ощутимо сокращается. Вот код на Delphi:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure injection(var A: TArray; min, max: Integer);
var i, j, k, tmp: Integer;
  function seek(min, max, T: Integer): Integer;
  begin
    Result:=min+Round((max-min)/2);
    if max-min<=1 then
      Result:=Result+1 else
    if T<A[Result]
      then
        Result:=seek(min, Result, T)
      else
        Result:=seek(Result, max, T)
  end;
begin
for i:=min+1 to max do
  begin
    if A[i]>=A[i-1] then continue;
    if A[i]<A[min]
      then j:=min
      else j:=seek(min, i-1, A[i]);
    tmp:=A[i];
    for k:=i downto j+1 do
      A[k]:=A[k-1];
    A[j]:=tmp;
  end;
end;

   Для поиска места вставки процедура сортировки использует внутреннюю рекурсивную функцию seek, реализующую метод половинного деления, постепенно уменьшающий область поиска до искомого индекса. Попробуйте вставить эту процедуру в код программы на странице Обзор алгоритмов сортировки, сравнивающей разные алгоритмы сортировки, и оцените выигрыш по скорости. Мой результат - на сортировку миллиона чисел вместо 17 минут новый алгоритм затратил всего 7 минут!