When is the appropriate time to use Radix Sort?

Question

What are the constraints on your data for you to be able to use Radix sort?

If I'm sorting a large list of integers, would it be appropriate to use Radix sort? Why is Radix sort not used more?

Answer 1

It's great when you have a large set of data with keys that are somehow constrained. For example, when you need to order a 1-million array of 64-bit numbers, it can be used to sort by 8 least significant bits, then by the next 8, and so on (applied 8 times). That way this array can be sorted in 8*1M operations, rather than 1M*log(1M).

Answer 2

If you know the range of the integer values, and it's not too large,
maybe counting sort would be a better choice in your case.

Answer 3

One reason you might not see it as often as you'd think you would is that Radix sort is not as general purpose as comparison based sorts (quicksort/mergesort/heapsort). It requires that you can represent the items to be sorted as an integer, or something like an integer. When using a standard library, it is easy to define a comparison function that compares arbitrary objects. It might be harder to define an encoding that properly maps your arbitrary data type into an integer.