This post is to discuss some implementation of radix sort, which varies from bucket sort. To simplify the case, we are going to sort an array of positive integers. At the end of this post, I will discuss how to extend it to other data.

So the first question is **how many buckets we need**. One straight answer is 10, if you think integers as decimal. Why don’t we use 2, 8, 16? One integer can be represented as binary, octal or hexadecimal. Actually, you can choose any number as the number of buckets. Then, the question will be **How to decide the number of buckets**. More bucket, less times of loop. And, more bucket results for less items in a single bucket, which is good for the case with a large amount of input.

The implementation with 10 buckets is easy to find online. The following is an implementation with two buckets. Think it twice before we start. Once we use two buckets, we can use one. bucket[1] is always equivalent to n – bucket[0]. Thus, the implementation looks like counting sort on the bits one by one.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
void bucket_sort(int A[], int n) { // we need O(n) extra space int *curr = (int *)malloc(n * sizeof(int)); int *prev = A; int *swap; // To exam bits one by one int level; int i; int b0_idx, b1_idx; // Counting int bucket0; for (level = 0; level < 8 * sizeof(int) - 1; ++level) { bucket0 = 0; // Counting how many int with 0 at the level-th // bit (from right) for (i = 0; i < n; ++i) { if (! ((prev[i] >> level) & 1)) ++bucket0; } // refresh the result b0_idx = 0; b1_idx = 0; for (i = 0; i < n; ++i) { if ((prev[i] >> level) & 1) { curr[bucket0 + b1_idx] = prev[i]; ++b1_idx; } else { curr[b0_idx] = prev[i]; ++b0_idx; } } swap = curr; curr = prev; prev = swap; } // Update A and free the allocated memory if (prev != A) { for (i = 0; i < n; ++i) A[i] = prev[i]; free(prev); } else { free(curr); } } |

The implementation above takes O(n * log(sizeof(int))) time, and O(n) space. Actually, time complexity can be reduced to O(n * log(sizeof(max_element))) with a small modification on the code.

One problem is left, **How to extend this algorithm to other data**. The solution will be easy if the data is or can be represented by a sequence of bits. Or, we have to find a way to classify the given items, which depends on cases.