Right (LSB) radix -- how to handle the 2's complement?

Question

I am attempting to implement a right/LSB radix sort for integers, and once it's working, I will try to parallelize it. My sequential code works well for unsigned numbers, but once I throw negative integers at it, it doesn't "see" the signed bit and ends up with positive (sorted) integers from 0 to n mixed with negative (again, sorted) integers from -n to -1.

Here's my code:

public class SeqRadix {
    static void radix2(int[] a) {

        // 2 digit radixSort: a[]
        int max = a[0];
        int numBit = 2;
        int n = a.length;

        // a) find max value in a[]
        for (int i = 1; i < n; i++){
            if (a[i] > max) {
                max = a[i];
            }
        }
        while (max >= (1 << numBit)){
            numBit++; // digits in max
        }
        // decide num of bits in bit1 and bit2
        int bit1 = numBit / 2, bit2 = numBit - bit1;
        int[] b = new int[n];
        radixSort(a, b, bit1, 0); // first digit from a[] to b[]
        radixSort(b, a, bit2, bit1);// second digit, back from b[] to a[]
    } // end

    /**
     * Sort a[] on one digit ; number of bits = maskLen, shiftet up �shift�
     * bits
     */
    static void radixSort(int[] a, int[] b, int maskLen, int shift) {
        int acumVal = 0, j, n = a.length;
        int mask = (1 << maskLen) - 1;
        int[] count = new int[mask + 1];

        // b) count=the frequency of each radix value in a
        for (int i = 0; i < n; i++) {
            count[(a[i] >> shift) & mask]++;
        }

        // c) Add up in 'count' - accumulated values
        for (int i = 0; i <= mask; i++) {
            j = count[i];
            count[i] = acumVal;
            acumVal += j;
        }
        // c) move numbers in sorted order a to b
        for (int i = 0; i < n; i++) {
            b[count[(a[i] >> shift) & mask]++] = a[i];
        }
    }// end radixSort
}// end SekvensiellRadix

As it first sorts on the LSBs, then more and more significant bits, that last 2's complement/signed bit doesn't get caught it seems. Thanks in advance!

Answer 1

What you need to do is invert the comparison operation on the sign bit. For every other bit, 0 < 1, but for the sign bit we use 1 < 0. As you sort bits 0 through 30 (for 32-bit integers, obviously), you sort the magnitude of that integer. Not absolutely, because there's that one-shift, but relative to all other integers of the same sign, which is all we need.

So, if we have the numbers {5, -1, 3, 2, -3, -8} (signed 4-bit for simplicity):

0101 =  5
1111 = -1
0011 =  3
0010 =  2
1101 = -3
1000 = -8

After sorting up to bit 2 we have:

1 000 = -8
0 010 =  2
0 011 =  3
0 101 =  5
1 101 = -3
1 111 = -1

Notice that each of the negative numbers are sorted in increasing order relative to the other negative numbers. (Likewise for the positives.) Now, for the comparison of the sign bit we say 1 < 0. That will move all of the negative numbers to the front of the list and, since we're using a stable sorting mechanism, all of the negative numbers stay in the same position relative to each other. (Again, likewise for the positives.)

In the end we have our list sorted in ascending order:

1000  = -8
1101  = -3
1111  = -1
0010  =  2
0011  =  3
0101  =  5

Answer 2

You simply need to convert all int values to unsigned by inverting bit 31 when making decisions on them:

unsigned = signed ^ 0x80000000;

Alternately, if you find that more convenient to implement, reverse the result of all decisions made based on bit 31.

Edit: That already starts when you try to find the max value - the way you search for the max you will never find a value with bit 31 set as max. You need to use unsigned comparison (which java doesn't support by language means) there as well, so flip bit 31 before comparing:

    // a) find max value in a[]
    for (int i = 1; i < n; i++){
        if ((a[i]^0x80000000) > (max^0x80000000)) {
            max = a[i];
        }
    }