/* Counting sort 

Considere um vetor v com n elementos no intervalo [0,9999] 
(o intervalo é conhecido a priori). Queremos ordenar os elementos 
do vetor em ordem crescente. 

*/
     
#define MAX 10000
     
void countingsort (int v[], int n) {
  int conta[MAX], i, k;
  for (i = 0; i < MAX; i++)
    conta[i] = 0;
  for (i = 0; i < n; i ++)
    conta[v[i]]++;
  /* na posição conta[i] temos o número de ocorrências de i no vetor v */
  k = 0;
  for (i = 0; i < MAX; i++)
    while(conta[i] > 0){
      v[k] = i;
      k++;
      conta[i]--;
    }
}