Java Bit Operations (In Radix Sort)

Question

The other day I decided to write an implementation of radix sort in Java. Radix sort is supposed to be O(k*N) but mine ended up being O(k^2*N) because of the process of breaking down each digit to one number. I broke down each digit by modding (%) the preceding digits out and dividing by ten to eliminate the succeeding digits. I asked my professor if there would be a more efficient way of doing this and he said to use bit operators. Now for my questions: Which method would be the fastest at breaking down each number in Java, 1) Method stated above. 2) Convert number to String and use substrings. 3) Use bit operations.

If 3) then how would that work?

Answer 1

http://en.literateprograms.org/Radix_sort_(Java)

The line of code that does this;

 int key = (a[p] & mask) >> rshift;

is the bit manipulation part.

& is the operator to do a bitwise AND and >> is a right-shift.

Answer 2

As a hint, try using a radix other than 10, since computers handle binary arithmetic better than decimal.

• x >>> n is equivalent to x / 2ⁿ
• x & (2ⁿ - 1) is equivalent to x % 2ⁿ

By the way, Java's >> performs sign extension, which is probably not what you want in this case. Use >>> instead.

Answer 3

I don't know of any way to use only bit manipulations to convert an arbitrary in integer into an array of decimal digits (which it sounds like you are trying to do).

I took a look at the implementation of Integer.toString(). It basically does a mod by 10 then divide by 10, over and over. They use some bit manipulation tricks to avoid actually using multiplication or division operations. If this is what your professor meant, then I guess there are some bit manipulation tricks, but I don't think that is the same thing.

As mentioned by erickson, there is no need to perform the radix sort in base 10. It would be much faster to sort in base 16. So, for example, to get the i^th-least-significant hex digit of an integer n:

int digit = (n >>> (i<<2)) & 0xf;

(Note that i<<2 is just another way of writing i*4)

For 32-bit integers, there are up to 8 hex digits, so radix sort in base 16 should give O(8*n) == O(n) performance. Also, I'm not sure if this will work properly if negative values are allowed.

Answer 4

I should add that, for me, Arrays.sort(int[] x) was still much faster than my implementation of radix sort on an array of 1 million integers, even though in theory radix sort should be faster.