Why quicksort is more popular than radix-sort?

Question

Why quicksort(or introsort), or any comparison-based sorting algorithm is more common than radix-sort? Especially for sorting numbers.

Radix-sort is not comparison based, hence may be faster than O(n*logn). In fact, it is O(k*n), where k is the number of bits used to represent each item. And the memory overhead is not critical, since you may choose the number of buckets to use, and required memory may be less than mergesort's requirements.

Does it have to do with caching? Or maybe accessing random bytes of integers in the array?

Answer 1

One obvious answer is that you can sort arbitrary types using quicksort (ie anything that's comparable), while you are restricted to numbers only with radix. And IMO quicksort is a lot more intuitive.

Answer 2

Two arguments come to my mind:

1. Quicksort/Introsort is more flexible:

   Quicksort and Introsort work well with all kinds of data. All you need for sorting is the possibility to compare items. This is trivial with numbers but you can sort other data as well.

   Radix sort on the other hand just sorts things by their binary representation. It never compares items against each other.

2. Radix sort needs more memory.

   All radix sort implementations that I've seen use a secondary buffer to store partial sorting results. This increases the memory requirements of the sorting algorithm. That may not be a problem if you only sort a couple of kilobytes, but if you go into the gigabyte range it makes a huge difference.

   If I remember right a in place radix-sort algorithm exist on paper though.

Answer 3

Radix sort is slower for (most) real world use cases.

One reason is the complexity of the algorithm:

If items are unique, k >= log(n). Even with duplicate items, the set of problems where k < log(n) is small.

Another is the implementation:

The additional memory requirement (which in it self is a disadvantage), affects cache performance negatively.

I think it is safe to say that many libraries, like the standard library, use Quicksort because it performs better in the majority of cases. I don't think that "difficult implementation" or "less intuitive" are major factors.