When should we use Radix sort?

It seems Radix sort has a very good average case performance, i.e. O(kN):

Yet it seems like most people are still using Quick Sort - why is this?


  • Quick sort has an average of O(N logN), but it also has a worst case of O(N^2), so even due in most practical cases it wont get to N^2, there is always the risk that the input will be in "bad order" for you. This risk doesn't exist in radix sort. I think this gives a great advantage to radix sort.