2
$\begingroup$

I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even questions on the internet where it is asked to prove that a sorting algorithm cannot be faster than $n \log (n)$.

Wanted to have a clarification on this. Does radix sort have any limitations? If not, is the lower bound on sorting linear in the number of elements?

  • 0
    @froggie Almost, take the example of $256_{(10)}$, the number of bits required for it is $9$, contrary to the output of $log_2(256) = 8$. That's because in an $n$-bit binary value, the highest power is $2^{n-1}$ which would be, in the case of 8 bits, $128$. The highest value expressible, therefore, is $2^n - 1$ (for all bits to be $1$, evaluating to $255$). Therefore, the actual number of bits required for $n$ is $log_2(n)+1$ (trunc the fractional part). Therefore, you actually can only express $n$ with that many bits, even though a lot more falls into that range ($n_{max}=2^{log_2(n)+1}-1$).2012-05-24

1 Answers 1

2

The number of bits $k$ cannot be considered constant in general. In fact, if all the $n$ numbers are distinct then $k = \mathcal{\Omega}(\log n)$. Hence, there is no difference between radix sort and other fast sorting algorithms.

More generally, any generic deterministic sorting algorithm cannot better $\mathcal{O}(n \log n)$ complexity. If you have $n$ numbers, then the number of comparisons you need to make is at least $\log_2(n!)$.

  • 2
    The nlogn lower bound is applicable only to comparison based sorts. There are other sorts with almost linear time complexity (of course they have other bizarre shortcomings making them impractical) For example, [Counting Sort](http://en.wikipedia.org/wiki/Counting_sort)2012-05-24