A 1 dimensional implementation of beadsort. O(MN) where M is maxint.

beadsort.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void sort(int A[], int N) {
    int i,count;
    int *R = calloc(N,sizeof(int));
    do {
       count=0;
       for (i=0;i<N;i++) { if (A[i]) { count++;  A[i]--;} }
       for (i=0;i<count;i++) { R[i]++; }
    } while(count);
    memcpy(A,R,N*sizeof(int));  //A is now sorted descending.
    free(R);
 }

int main(int c, char* argv[])
{
   int vals[] = {2,5,4,2,4,6,8,22,4,2,3,6,2,4,533,0,2,0};
   int i,n = sizeof(vals)/sizeof(*vals);
   for (i=0;i<n;i++){
      printf("%d ",vals[i]);
   }
   printf("n=%d\n",n);
   sort(vals, n);
   for (i=0;i<n;i++){
      printf("%d ",vals[i]);
   }
   printf("n=%d\n",n);
   return 0;
}