Hello, I have been asked to provide an algorithm for the following:

You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.

I have been unable to find any way to do it, due to the lack of a "hard" upper bound on the input range (Which varies with the size of input).

I'll be happy to hear ideas for anyone who can offer help. Thanks !