Trier un tableau en temps linéaire

Question

J'ai besoin de trouver une méthode pour trier un tableau dans $ o (n) $ complexité du temps. J'ai vu ce lien, mais je ne sais pas comment l'appliquer aux éléments dont j'ai besoin.

Saisir: un tableau $ a $ de longueur $ n $, contenant des valeurs de 1 $ à $ n ^ 2 $

Production: un tableau triée $ a $

Quelqu'un peut-il expliquer en pseudocode ou en mots comment faire cela?