Come ordino questi elementi in o (n) tempo?

Question

Quindi diciamo che ho una serie di elementi in cui ciascuno dei valori può variare da 0 a $ n^2-1 $. Sto cercando di creare un algoritmo per ordinare questo array in O (N) tempo di esecuzione e stavo pensando di usare Radix Sort. Il tempo di esecuzione di RADIX è O (d (n+n)) o O (dn) se n è davvero grande. Quindi, come posso modificare RADIX Ording in modo che funzioni in O (N)?

EDIT: Non credo che voi ragazzi lo capisca. La quantità di elementi nell'array è n ma il valore effettivo per ciascun elemento può variare da 0 a n^2 - 1. Quindi se abbiamo un array con 10 elementi al suo interno, il più grande l'elemento può essere 99 e il più piccolo Può essere 0 ma ci saranno ancora 10 elementi nell'array.