given an array A of n numbers in range $1$ to $nlogn$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $nlogn$.

given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $n\log n$.

given an array A of n numbers in range $0$ to $nlogn-1$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $nlogn$.

given an array A of n numbers in range $1$ to $nlogn$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $nlogn$.