Why bother with comparison sorts?

Question

Algorithms like Timsort, Quicksort & Mergesort dominate the "real world" sorting methods. The case for these comparison sorts is quite practical — they've been shown to be the most performant, stable, multipurpose sorting algorithms in a wide variety of environments.

However, it seems like nearly everything that we would sort on a computer are countable / partially ordered. Numbers, characters, strings, even functions are amenable to some meaningful non-comparison sorting method. A candidate here is Radix sort. In general it will behave faster than O(n*log(n)), beating the theoretical comparison sort limit of n * log(n) by a wide margin in many cases with a complexity of O(K*n) -- K being the number of bits that are required to represent a particular item.

What gives?

Answer 1

The speed of radix sort depends on the length of the key. If you have long keys like strings, radix sort may be very slow.

Further, for sorting only a few items the initialization costs may outweight the actual sorting by a magnitude.

For instance if you sort 32 bit integers by using a 8 bit radix you need to initialize at least 4 times the list of 256 buckets - if you only have 20 or so items to sort this and the 80 swaps will be far slower than the about ~200 comparisons/swaps a quicksort needs.

If you sort anything longer, like strings, you have for each character of the longest string a bucket initialization - this may be even worse.

Answer 2

Comparison sorts are based on a really nice abstraction: all you need is a way to compare two elements. Then, depending on your language, with templates (c++), interfaces (java), typeclasses (haskell), function objects (javascript) etc.. you can sort containers which can hold arbitrary types, the only thing you need is implement the comparison.

How would you implement Radix sort for arbitrary types? :)

Answer 3

Radix sort it's useful only for sorting objects with integer keys, and from a practical performance point of view it depends heavily on the length of the keys. For the general case of sorting arbitrary objects, this won't be enough - hence the necessity for comparison-based sorting.