Cuando trabaje en "El tipo más rápido para BrainF *** ", Descubrí este algoritmo, que es O (N * k), donde k es el valor máximo en la entrada. Requiere O (N) de almacenamiento adicional.

La analogía física es que tienes N pilas de tokens. La altura de la pila representa el valor a ordenar. (Cada ficha representa un poco). Reserva espacio para otras N pilas. Sacas una ficha de la parte superior de cada pila que tiene fichas, y luego agregas una a cada pila en el nuevo conjunto de derecha a izquierda hasta que tu mano esté vacía. Repita hasta que todas las pilas originales estén vacías. Ahora el nuevo conjunto está ordenado ascendente de izquierda a derecha

Cía

 void sort(int A[], int N)
 {
    int *R = calloc(N,sizeof(int));
    do {
      int i,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);  //A is now sorted descending.
    free(R);
 }

¿Tiene este algoritmo un nombre? Parece similar a unaBead Sort, pero no creo que sea lo mismo.