Ordinamento di un array in tempo lineare

Question

Devo trovare un metodo per ordinare un array in $ o (n) $ complessità temporale. vidi questo linkTuttavia, non sono sicuro di come applicarlo agli elementi di cui ho bisogno.

Ingresso: un array $ a $ di lunghezza $ n $, contenente valori da $ 1 $ a $ n^2 $

Produzione: un array ordinato $ a $

Qualcuno può spiegare in pseudocodice o in parole Come farlo?