Сортировка подсчётом

Создадим массив счётчиков для всех возможных значений в сортируемом массиве. За один проход подсчитаем количество вхождений каждого значения. Заполним результат подсчитанными значениями.

type
  TAI = array of integer;
...  
procedure CountingSort(var A: TAI);
var
    Counters : TAI;
    i,ii,j   : Integer;
    Min, Max : integer;
begin
  // Найдём границы диапазона.
  Min := High(A[0]);
  Max :=  Low(A[0]);
  for i:= Low(A) to High(A) do
  begin
    if A[i]>Max then Max := A[i];
    if A[i]<Min then Min := A[i];
  end;
  // Создаём счётчики.
  SetLength(Counters, Max-Min+1);
  // Считаем количество вхождений.
  for i:= Low(A) to High(A) do
  begin
    inc(Counters[A[i]-Min]);
  end;
  // Заполняем результат.
  j:=0;
  for i:= Low(Counters) to High(Counters) do
  begin
    for ii := 1 to Counters[i] do
    begin
      A[j] := i + Min;
      inc(j);
    end;
  end;
end;

По понятным причинам область самостоятельного применения этого алгоритма невелика.   

Не эффективно использовать его в случае, когда количество допустимых значений велико (например,   -2147483648..2147483647) или вовсе бесконечно (например, сортировка вещественных чисел).

Сложность: