program contagem;

const MaxTam = 40000000;
       
type ChaveTipo = integer;
     Item = record 
              Chave: ChaveTipo;
              { outros componentes }
            end;
     Indice   = 0..MaxTam;
     Vetor    = array [Indice] of Item;
     Contador = array [Indice] of integer;

var A: Vetor;
    B: Vetor;    { Vetor auxiliar usado dentro do procedimento Contagem }
    C: Contador; { Arranjo auxiliar usado dentro do procedimento Contagem }
    i: Indice;
    n: Indice;
    k: integer;

procedure Contagem (var A: Vetor; 
                    var n: Indice; 
		    var k: integer);
var i: Indice;
begin
  for i := 0 to k do C[i] := 0;
  for i := 1 to n do C[A[i].Chave] := C[A[i].Chave] + 1;
  for i := 1 to k do C[i] := C[i] + C[i-1];
  for i := n downto 1 do
    begin
    B[C[A[i].Chave]] := A[i];
    C[A[i].Chave] := C[A[i].Chave] - 1;
    end;
  for i := 1 to n do A[i] := B[i];
end; { Contagem }

procedure Imprime (var V: Vetor; var n: Indice);
begin
  for i := 1 to n do write (V[i].Chave,' ');
  writeln;
end;

procedure Testa (var V: Vetor; var n: Indice);
begin
  for i := 2 to n do
    begin
    if V[i].Chave < V[i-1].Chave
    then begin
         write ('ERRO: ');
         Imprime (V, n);
         halt;
         return;
         end;
    end;
  write ('OK: ');
  Imprime (V, n);
end;

begin
  n := 10; {Tamanho do arranjo a ser ordenado}
  randomize;
  for i := 1 to n do
    begin
    A[i].Chave := 1 + random (n);
    end;

  write ('Desordenado : ');
  Imprime (A, n);

  write ('Contagem  ');
  k := n;
  Contagem (A, n, k);
  Testa (A, n);
end.