Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$?
Best time complexity is O(n).
Refer below link for reference
Using merge, heap sort will get O(nlogn)
But using radix sort will get in linear time only. O(n)
Reference : https://stackoverflow.com/questions/12042107/sort-n-numbers-between-0-n2-1-in-on