1void countingSort(int* A, int n) {
2 int i, max = A[0];
3 for(i=1;i<n;i++) if(A[i]>max) max=A[i];
4 int* count = (int*)calloc(max+1, sizeof(int));
5 int* output = (int*)malloc(n*sizeof(int));
6 for(i=0;i<n;i++) count[A[i]]++;
7 for(i=1;i<=max;i++) count[i]+=count[i-1];
8 for(i=n-1;i>=0;i--) output[--count[A[i]]]=A[i];
9 for(i=0;i<n;i++) A[i]=output[i];
10 free(count); free(output);
11}
