September Writing Challenge Post 12: TIL, Radix Sort Edition

It occurred to me over coffee this morning that I’d never implemented my own radix sort; so, while the caffeine kicked in, I did that, and I learned a few things.

(Everything below applies only to my radix sort implemented in Objective-C in Xcode 6.4 on a machine with an Intel Core i7 processor, sorting a list of a million pseudorandom positive integers with values in the interval [0, 108). YMMV.)

Once I got the sort implemented and performance tests set up, the first thing I did was to parametrize it by radix. When you see a radix sort demonstrated in books, you always see it done in base 10. Unless the numbers were represented as strings, that always just seemed weird and unnatural to me, so I experimented with different radices. For my less-than-rigorous test, a base 2 sort took about 3 times longer than a base 10 sort, which was slightly slower than a base 16 sort. Base 100 was faster still.

This makes sense: Radix sort time complexity is O(kN), with N as the number of elements to sort and k as the maximum number of digits in the radix you’ve chosen. Radix goes up, k goes down. Gist and code:

With that finding, I wondered how much better you could do choosing a power-of-2 radix, and doing a little bit bashing – Objective-C is still a superset of C, and things like the C bit-shift operators are native instructions on Intel processors, so I figured I might be able to squeeze a little more performance out of my sort by eschewing % and / in favor of >> and &. I was correct – I can get almost a 2x improvement using bit manipulation over arithmetic operations in the base 2 and base 16 sorts. Gist and code:

Notes:

  • I realize I am discovering nothing new here. These were just my own learnings from poking around over coffee.
  • It should not come as a surprise that bad things happen when you add negative numbers to your test set (at least with this implementation).
  • Moving to base 256 with signed int test data and the range of numbers I was working with led to more bad things happening.
  • Maybe I’ll have some more coffee.

Leave a Reply

Your email address will not be published. Required fields are marked *