@DanielFischer Also, I found at a site the following:
Let there be d digits in input integers. Radix Sort takes $O(d \cdot (n+b))$ time where $b$ is the base for representing numbers, for example, for decimal system,$ b$ is $10$. Since $n^2-1$ is the maximum possible value, the value of $d$ would be $O(\log_b(n))$. So overall time complexity is $O((n+b) \cdot \log_b(n))$. Which looks more than the time complexity of comparison based sorting algorithms for a large $k$. The idea is to change base $b$. If we set $b$ as $n$, the value of $O(\log_b(n)) $ becomes $O(1)$ and overall time complexi…