Radix sort

About a year ago, I decided to take a serious look at radix sort — one of those algorithms that everyone covers in school and then forgets, because everyone knows that it only works for some narrow special cases with lots of edges.

Turns out that you can make radix sort very general, with base behaviour equal to production-quality quicksort, and typical speed around five times that of quicksort. In a nutshell, it can be done with a MSB-first radix sort, that scans keys 16 bytes at a time, building statistics, then performs the usual radix-sort scatter and gather passes. Each pass splits a set of runs into a larger set of smaller runs, and very small runs are sorted with insertion sort.

For a full description with pictures, check out this GoogleDoc. Still haven’t decided whether to release the source code under GPL or BSD license; more to come.

Advertisements

About mischasan

I've had the privilege to work in a field where abstract thinking has concrete value. That applies at the macro level --- optimizing actions on terabyte database --- or the micro level --- fast parallel string searches in memory. You can find my documents on production-system radix sort (NOT just for academics!) and some neat little tricks for developers, on my blog https://mischasan.wordpress.com My e-mail sig (since 1976): Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection.
This entry was posted in algorithm, Uncategorized and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s