Русская сортировка половинками

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

procedure ThanosSort(var A: TAI);

   procedure Thanos(left, right: integer);
   var
       buff : TAI;
       sum  : Int64;
       i    : Integer;
       mean : real;
       l, r : integer;
   begin
     if right > left then
     begin
       // Считаем среднее.
       sum := 0;
       for i := left to right do
         sum := sum + A[i];
       mean := sum / (right-left+1);
       // выделяем вспомогательный буфер 
       SetLength(buff, right-left+1);
       // Разделяем элементы на две корзины.
       l := 0; r := High(buff);
       for i := left to right do
       begin
         if A[i]>mean then
         begin
           buff[r] := A[i];
           dec(r);
         end
           else
         begin
           buff[l] := A[i];
           inc(l);
         end;
       end;
       // Возвращаем результат.
       for i := left to right do
         A[i] := buff[i-left];

       r := right - (High(buff) - r) +1;
       l := left + l - 1;
       SetLength(buff, 0);
       // При необходимости, досортируем каждую корзину рекурсивно.
       if l < right then
       begin
         Thanos(left, l);
         Thanos(r, right);
       end;
     end;
   end;

begin
  Thanos(Low(A), High(A));
end;