Алгоритм сортировки вычерпыванием

[F.Ury]

Кто-нибудь знает как работает этот алгоритм, ну или есть готовый исходник сортировки?

[F.Ury]

Я нешел, можете не искать, вот если кому-нибудь понадобиться на Паскале:
type
atype = array [1 .. 100] of real;
....

0 <= a[i] <= m

//Передается строка чисел "a" для сортировки, а также размерность её n и максимальный из элементов m
//Возвращается отсортированная по возрастанию строка
procedure SortV(n,m: integer; var a: atype);
var
b: array [0 .. 1000, 20] of real;
c: array [0 .. 1000] of integer; //Т.е программа будет работать только с max(a)<=1000.0
i, j, k :integer;

begin
//Заполняем нулями массив c[i]
for i:=0 to 99 do c[i]:=0;

//Цикл в котором массив a делится на 0m-1) "черпаков"
for i:=1 to n do
begin
j:=trunc(a[i]); //Номер черпака(столбца матрицы b) равен целой части a[i]
c[j]:=c[j]+1; //Прибавляем кол-во элементов в столбце j
b[ j , c[j] ]:=a[i]; //Ставим элемент a[i] в конец столбца с номером j (либо 1-ым, если столбец еще пустой)

end;

//Сортировка данных внутри черпаков (любым методом, например прямого перебора с формированием отсортир. массива)
for i:=1 to m do
if c[i]>0 then //Если i-черпак не пустой
sort2(b, c, i); //Передаем матрицу "b", вектор "c" с кол-вом элементов в черпаках и индекс i для сортировки в i-ом черпаке.
//Сортировка должна вестись по 2-му индексу матрицы "b" - т.е. для каждого из столбцов.

//Предполагаем, что на выходе процедуры Sort2 имеем матрицу b с отсортированными по возрастанию данными в каждом из столбцов, т.е. b[i,k]<=b[i,k+1], для любых допустимых (k, i).

//Выстраиваем вектор a из уже отсортированных содержимых "черпаков" b[i, k]
i:=1;
j:=1;
while (i<= m) do
begin
if c[i]>0 then begin
for k:=1 to c[i] do begin
a[j]:=b[i, k];
j:=j+1;
end; //for
end; //if
i:=i+1;
end; //while

end; //proc
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Пример:
a=[3, 5, 1, 2]
n=4 - элементов строки
m=5 - максим. число

В рез-те имеем после деления на черпаки b=|| 1, 2, 3, 0, 5, ... , 0|| , c=[1, 1, 1, 0, 1] - вектор количеств элементов в каждом черпаке.
|| 0, 0, 0, 0, 0, ..., 0||
|| .., .., .., .., .. ||
|| 0, 0, 0, 0, 0, ..., 0||
В данном примере в "b" нам интересны только первые 5 элементов,остальные - нули.
Сортировка внутри черпаков здесь не нужна, т.к. в каждом столбце один элемент - в случае дробных чисел могут появиться несколько элементов в столбцах, например если в векторе "a" есть элементы 3.5, 3.8 - они окажутся оба в 3-м столбце (см.алгоритм)

В результате последнего цикла получаем a=[1,2,3,5].