Se io ho un array di 100 con elementi che hanno valori che vanno da 0 a 100, però disordinati (es.: 9,99,51,.... fino a coprire tutti i valori), posso ordinarlo così:
codice:
int v[100];  // vetore da ordinare
int aux[100]; // vettore ausiliario
....
for(i=0;i<100;i++)
    aux[v[i]]=v[i];
Però solo in questo caso, perchè i valori sono consecutivi.E inoltre se i valori sono troppo grandi si consuma troppa memoria.

Ora mi sto scervellando per capire se si può avere un algoritmo di ordinamento con complessità O(n) anche se i valori non sono consecutivi.
Ad esempio se ho un array di 100 elementi con valori compresi tra -1000 e +1000,senza ripetizioni,posso fare così:
codice:
int v[1000];   // vettore da ordinare
...
int aux[2000];     // vettore ausiliario
int *p;
p=&aux[1000];
for(i=0;i<100;i++)
    p[v[i]]=v[i];
Però si può farlo solo per casi banali come questi, e comunque occupando tanta memoria.E inoltre una volta avuto il vettore aux di 2000 elementi, non so da dove iniziare a leggere i valori.
Mi chiedevo se è possibile ora, avendo il vettore aux, capire quali valori stampare usando un algoritmo con complessità O(n).