Ordenando sin comparar

Normalmente se dice que un algoritmo óptimo para ordenamiento de una secuencia de números tiene que realizar nlogn comparaciones donde n es el número de elementos de del arreglo. Esto se maneja como una regla (de hecho es la complejidad de algoritmos como MergeSort, HeapSort y en el mejor de los casos de QuickSort).

Ahora les voy a presentar un algoritmo que requiere 0 comparaciones y que tiene una complejidad de O(n) (para ser específicos O(2n)), es una variante de algo llamado RadixSort y el único impedimento es que funciona para valores que están en un rango de 1 a n cuadrada (donde n es de nuevo el número de elementos del arreglo).

Lo escribo en pseudo-C y trabaja con tablas hash:

Radix(int[] c){
  hash a,b;
  n= length(c);
  for(i=0;i<n;i++) inserta(c[i],a,mod(c[i],n));
  for(i=0;i<=n;i++){
    while(!(vacia(a,i))){
       aux=saca(a,i)
       inserta(aux,b,aux/n);
       }
    }
  return b;
  } 

Con la división de aux/n, me refiero a la parte entera de la división, ¿Vieron alguna comparación?, pruebenlo y verán que funciona (solo no hay que olvidar el rango de 1 a n cuadrada).

Otro detalle, este algoritmo regresa la lista ordenada en una tabla hash, si queremos que lo regrese en un arreglo, se puede implementar otros 2 ciclos (for, while anidados) que saquen los elementos de b y los metan en otro arreglo aunque esto aumenta la complejidad a O(3n), pero sigue siendo muy lineal (osea O(n))

No sé para que lo postee, puede que a alguien le sirva y me pareció una demostración de que no hay que casarse con las ideas, siempre nos enseñaron Ordenamiento con comparaciones, parecería que estuvieran casados... podemos ver que no. Saludos.