sorting - Sort array of n integers in range [1, n^α], when α is a positive integer

Question

I am trying to think about an algorithm which sorts array of n integers in range in time complexity , where is a positive integer.

I can't use Counting sort, since the time complexity will be .

How can I use the information about the range of the numbers, and sort the array, when iterating over the range is impossible?

question from:https://stackoverflow.com/questions/65643481/sort-array-of-n-integers-in-range-1-n%ce%b1-when-%ce%b1-is-a-positive-integer

Answer 1

Waitting for answers