I think a counting sort type auxiliary array can be used to keep track of the frequency of each number. A hash table can also be used. But, all these result in O(n) space. I am not sure if O(1) space is possible.