Блочная сортировка

Она же Корзинная, она же Карманная... и даже Ведёрная... 

Идея состоит в том, чтобы разделить сортируемую последовательность на упорядоченные блоки(корзины, карманы) так, чтобы элементы в каждой корзине были гарантированно меньше элементов в корзине справа.

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

Например, если <Номер корзины> = <Значение> div N, то в корзину с номером 0 попадут элементы со значениями от 0 до N-1, в корзину с номером 1 - значения от N до 2*N-1 и т.д.

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

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

Если корзин две, и правило сортировки - сравнение со значением срединного элемента, то мы получаем быструю сортировку.

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

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

Блочная сортировка в общем виде:

type
  TAI = array of integer;
...

procedure BucketSort(var A: TAI);
const
      N = 4; // Количество корзин
var
    i : integer;
    Bucket: TList<integer>;

    // Рекурсивная процедура сортировки корзины
    procedure _bucketSort(ABucket: TList<integer>);
    var
        Min, Max : integer;
        i,ii,j : integer;
        BucketSize : integer;
        buckets : array[0..N-1] of TList<integer>;

        Counters : TAI;

        // Хэш-функция, определяющая номер корзины.
        function GetIndex(Value: integer):integer;
        begin
          result := Value div BucketSize;
        end;

    begin
      // Определяем диапазон значений.
      Min := High(integer);
      Max := Low(integer);
      for i:= 0 to ABucket.Count-1 do
      begin
        if ABucket.Items[i]>Max then Max := ABucket.Items[i];
        if ABucket.Items[i]<Min then Min := ABucket.Items[i];
      end;
      // Определяемся с размером корзины.  
      BucketSize := (max-min+1) div N;
      // Если корзины ещё достаточно большие...
      if BucketSize>N then
      begin
        // Создадим нужное количество корзин.
        for i := Low(buckets) to High(buckets) do
          buckets[i]:=TList<integer>.Create;
        // Разложим входной список по корзинам.
        for i:= 0 to ABucket.Count-1 do
          buckets[GetIndex(ABucket.Items[i])].Add(ABucket.Items[i]);
        // Отсортируем каждую корзину по отдельности.
        for i := Low(buckets) to High(buckets) do
          _bucketSort(buckets[i]);
        // Соберём обратно результат.
        j :=0;
        for i := Low(buckets) to High(buckets) do
        begin
          for ii := 0 to buckets[i].Count-1 do
          begin
            ABucket[j] := buckets[i].Items[ii];
            inc(j);
          end;
        end;
        // Освободим ненужные корзины.
        for i := Low(buckets) to High(buckets) do
          buckets[i].Free;
      end
        else // Если входящий список маленький.
      begin
        // Тривиально отсортируем подсчётом.
        SetLength(Counters, Max-Min+1);

        for i:= 0 to ABucket.Count-1 do
        begin
          inc(Counters[ABucket.Items[i] - Min]);
        end;
        j:=0;
        for i:= Low(Counters) to High(Counters) do
        begin
          for ii := 1 to Counters[i] do
          begin
            ABucket.Items[j] := i + Min;
            inc(j);
          end;
        end;

      end;
    end;

begin
  // Перекладываем входной массив в список.
  Bucket := TList<integer>.Create;
  for i := Low(A) to High(A) do
    Bucket.Add(A[i]);
  // Запускаем сортировку.
  _bucketSort(Bucket);
  // Забираем результат обратно в массив.
  for i := 0 to Bucket.Count-1 do
    A[i] := Bucket.Items[i];
  Bucket.Free;
end;