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