LSD-сортировка

Least Significant Digit - вариант поразрядной сортировки, начиная с младших разрядов.

Идея состоит в том, чтобы сделать насколько проходов сортировки, при этом на каждом i-м проходе сортировать по значению младших k*i разрядов. Если использовать устойчивую сортировку, то на каждом проходе достаточно сортировать по k новых разрядов.

Например, если работать с двоичным представлением, то при сортировке по блоку в N бит можно использовать сортировку подсчётом и нам понадобится 2ⁿ счётчиков.

Посчитав, проведём сложение счётчиков. В каждый i-й счётчик сложим сумму всех счётчиков, которые левее. Теперь у нас в i-м счётчике будет не количество i-х элементов, а количество элементов, которое находится левее(т.е. позиция i-го элемента в отсортированной последовательности).

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

Вот код:

procedure LSDSort(var A: TAI);
const
      N = 8; // размер маски в битах
var
    Mask, MV : integer;
    buffer : TAI;
    Counters: TAI;
    i,j: Integer;
    cnt, tmp : integer;
    d: integer;

    // По исходному числу и номеру прохода
    //   возвращаем номер счётчика.
    function digit(AValue, I: integer):integer;
    begin
      result := (aValue shr (N*i)) and Mask;
    end;

begin
  // SizeOf(A[0])                     - размер элемента в байтах
  // SizeOf(A[0])*8                   - размер элемента в битах
  // (SizeOf(A[0])*8 + N - 1) div N   - необходимое количество проходов сортировки
  MV := 1 shl N;    // Диапазон значений от 0 до MV-1
  Mask := MV - 1;   // Маска заполнена единицами

  SetLength(buffer, length(A));
  SetLength(Counters, MV);

  for i := 0 to (SizeOf(A[0])*8 + N - 1) div N - 1 do
  begin
    // Обнуляем счётчики.
    for j:= Low(Counters) to High(Counters) do
      Counters[j] := 0;
    // Производим подсчёт.
    for j := Low(A) to High(A) do
      inc(Counters[digit(A[j], i)]);
    // Cкладываем счётчики.
    cnt := 0;
    for j := Low(A) to High(A) do
    begin
      tmp := Counters[j];
      Counters[j] := cnt;
      cnt := cnt + tmp;
    end;
    // Разворачиваем результат во временный буфер.
    for j := Low(A) to High(A) do
    begin
      d := digit(A[j], i);
      buffer[Counters[d]] := A[j];
      inc(Counters[d]);
    end;
    // Возвращаем результат в исходный массив.
    for j := Low(A) to High(A) do
      A[j] := buffer[j];
  end;
end;

Сложность: