Sorting radishes gives a nice demonstration of a part of radix sort (and, indeed, the both words stem from the same, well, root).

Suppose we have lots of radishes; we want to sort them into 3 categories: large, medium and small. Of course, looking at the size of each radish is inefficient. Here's how to do it better: get 2 grids with holes, one just large enough for small radishes to go through and the other just large enough for medium radishes to go through. Now put the radishes over the grid with small holes and shake. All the small radishes fall out, leaving the medium and large radishes. Take those and shake over the medium grid. The medium radishes fall out, and the large ones stay.

Agricultural packing plants actually do this sort (sorry) of thing to sort produce into sizes!

Great! So we can sort radishes without looking at the exact size; we just see which of 3 bins they filter into. What has that got to do with sorting algorithms?

A lot!

First, note that if we're not interested in any finer categorisation, this process actually sorts. So to sort an array of elements according to an order `small < medium < large`, we just need to go over the array once, putting each element into its bin. Of course, this works for any fixed number k of bins, and takes ~k n binning operations for n elements -- fast for k << log n.

But what if we have a rather larger number of bins? Say we want to sort values which fall into bins `000..999` (coded in decimal, say, so binning by each digit is fast) or `0..1023` (coded in binary, so binning by each bit is fast). Well, radix sort just performs our "radish sort" by increasing order of bins. In the first example, we'd first bin by units, then (preserving order) bin by tens, then by hundreds; in the second, we'd bin by the value of the j'th bit for j=0..9. Each binning stage is fast, so instead of O(n log n) comparisons, we require O(n log M) binnings, where we have M bins that are amenable to this treatment.

We also see (immediately) that this sort is not a stable sort: when we shook the radishes, we disturbed any existing pre-ordering that there may have been. For instance, if we pre-ordered them by the amount of dirt on each, after sorting by size we lose this pre-ordering -- dirty and cleaner radishes are mixed together.

So a radix sort is radically (sorry) different from most sorts. It requires a better understanding and decomposition of the comparison domain, but can yield very good results.

Log in or register to write something here or to contact authors.