Why quicksort is more popular than radix-sort?

Daniyar picture Daniyar · Aug 22, 2010 · Viewed 29k times · Source

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(nlogn). In fact, it is O(kn), 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

Nils Pipenbrinck picture Nils Pipenbrinck · Aug 22, 2010

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.