function sort( r : list ) : list;
var head, tail : array[1..M] of list;
i, j, h : integer;

begin
for i:=D downto 1 do begin
for j:=1 to M do head[j] := nil;
while r <> nil do begin
h := charac( i, r^.k );
if head[h]=nil then head[h] := r
else tail[h]^.next := r;
tail[h] := r;
r := r^.next;
end;
{*** Concatenate lists ***}
r := nil;
for j:=M downto 1 do
if head[j] <> nil then begin
tail[j]^.next := r;
r := head[j]
end
end;
sort := r
end;

list sort( r )
list r;

{
list head[M], tail[M];
int i, j, h;
for (i=D; i>0; i--) {
for (j=0; j while ( r != NULL ) {
h = charac( i, r->k );
if ( head[h]==NULL ) head[h] = r;
else tail[h]->next = r;
tail[h] = r;
r = r->next;
};
/*** Concatenate lists ***/
r = NULL;
for (j=M-1; j>=0; j--)
if ( head[j] != NULL ) {
tail[j]->next = r;
r = head[j];
}
};
return( r );
};