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, 10^{8}). 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
+ (void)paramRadixSort:(int*)input length:(int)l radix:(int)r { int max = [self findMax:input length:l]; int partiallySorted[l]; int i; int sigDig = 1; int bin[r]; while (sigDig < max) { for (int i = 0; i < r; i++) bin[i] = 0; for (i = 0; i < l; i++) bin[(input[i] / sigDig) % r]++; // get counts of current digits for (i = 1; i < r; i++) bin[i] += bin [i - 1]; // convert counts to array indices for (i = l - 1; i >= 0; i--) partiallySorted[--bin[(input[i] / sigDig) % r]] = input[i]; for (i = 0; i < l; i++) input[i] = partiallySorted[i]; sigDig *= r; } } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
+ (void)hexadecimalRadixSort2:(int[])input length:(int)l { int max = [self findMax:input length:l]; int partiallySorted[l]; int i; int powerOf16 = 0; int bin[16]; while ((1 << (powerOf16 << 2)) < max) { for (int i = 0; i < 16; i++) bin[i] = 0; for (i = 0; i < l; i++) bin[(input[i] >> (powerOf16 << 2)) & 0x0f]++; // get counts of current digits for (i = 1; i < 16; i++) bin[i] += bin [i - 1]; // convert counts to array indices for (i = l - 1; i >= 0; i--) partiallySorted[--bin[(input[i] >> (powerOf16 << 2)) & 0x0f]] = input[i]; for (i = 0; i < l; i++) input[i] = partiallySorted[i]; powerOf16++; } } |

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.