Массив длины N может содержать значения 1,2,3… N ^ 2. Можно ли выполнить сортировку за время O (n)?

Учитывая массив длины N. Он может содержать значения от 1 до N ^ 2 (N в квадрате) включительно, значения являются целыми. Можно ли отсортировать этот массив за время O (N)? Если возможно, то как?

Изменить: Это не домашнее задание.