Ah si, poi pensandoci bene ci sono riuscito.
Ho creato un array di interi,questo array (index, puntato da in) contiene 0 se a quell' indice non è associato nessun valore, 1 se a quell' indice è associato 1 valore, 2 se gli sono associato 2 valori ... con l' array di bool non si potevano contare le ripetizioni.
Quindi se index[0] vale 0, non c'è un elemento che vale 0 nell' array.Se index[10] vale 2, ci sono due elementi uguali a 10 nell' array.Scandisco tuto il vettore index e riscrivo i valori nel nuovo array.
Per ovviare al fatto che certi valori sono negativi, il puntatore a punta a un certo elemento dell' array aux.
Supponiamo che a punta a &aux[10] e chiamo a[-5], allora mi sto riferendo all' elemento aux[5].

Supponiamo che voglio ordinare la sequenza:{-9, 10, 2 , 4, 8, 8}, allora:
in[-9]=1;
in[10]=1;
in[2]=1;
in[4]=1;
in[8]=2;
con in=&index[9];


Insomma la funzione è questa:
codice:
void ordina(int *v,int n,int max, int min)
{
    int *index,*aux,*in,*a,i,k=0;
    aux=(int*)calloc((max-min),sizeof(int));
    index=(int*)calloc((max-min),sizeof(int));
    in=index;
    a=aux;
    if(min<0)
        for(i=0;i<abs(min);i++)
        {
            in++;
            a++;
        }
    for(i=0;i<n;i++)
    {
        a[v[i]]=v[i];
        in[v[i]]++;
    }
    for(i=0;i<(max-min);i++)
    {
        if(index[i]>0)
        {
            do
            {
                index[i]--;
                v[k++]=aux[i];
            }while(index[i]>0);
        }
    }
    free(index);
    free(aux);
}
Che è O(n+(max-min)), quindi se max-min è trascurabile rispetto a n, direi che è O(n).
n è la dimensione, max il massimo numero presente nell' array, min il minimo valore presente nell' array (anche negativo).
Ho concluso che è buono solo se n>>(max-min).