Question

1. Why is radix sort generally rejected by so many computer programmers?
2. Under what conditions does Radix-Sort run faster than O(n lg n) algorithms such as quicksort?
3. Under what conditions does Radix-Sort run slower than O(n lg n) algorithms such as quicksort?
4. How common are each of these conditions?
5. When do you think a sort such as radix sort would be useful?

Answer 1

1. Radix sort in general is rejected by computer programmers because it is not general, it is more of a specialized algorithm. Moreover other sorting algorithms like quicksort are flexible when used over multiple kinds of data. Radix sort is not much flexible. Also, the time complexity of radix sort is O(n) but when we say this, there is a constant also present in it. So to be precise the time complexity would be a*O(n) where a is some constant value. But in the cases of radix sort this value of a sometimes becomes very large, Thereby, increasing the time complexity. Also radix sort is not memory effecient. It consumes a lot of memory. Moreover Quicksort can also make use of hardware caches and thereby it's utility increased compared to radix sort. These are some of the main reasons why programmers generally tend to avoid radix sort.

2. Now consider a case when you have around a million data items to sort. These data items also contain repeated elements and there is an upper bound associated with them say 1000. Now radix sort will do it in 3*(1 Million) while quick sort will do it in 6*(1 Million). So, in case, when elements are in a fixed range and uniformly distributed, and also tend to repeat, then radix sort outperforms quicksort hugely.

3. Now, if the items are unique, then radix sort might perform poorly compared to other sorting algorithms like quicksort. In most of the cases, this scenario is there hence quicksort is preferred. Moreover, people tend to be unaware of the kind of data they are going to encounter while attempting to sort the data.

4. The cases in which radix sort performs poorly is more than in which it performs better when compared to quicksort. In most of the cases the presence of all items between a specific number range is not true. chances are there that data is completely new to you and you don't know much about it. Hence in general it is advisable to use quicksort unless there is a strong information about data and we know it will be better to use radix sort.

5. Whenever the longest value (or integer) is shorter than the array size, then radix sort will be helpful and better when compared to other algorithms like quicksort. In short you have a set of numbers where range is small and numbers are repeating than radix sort is used.

Hope that helps !!