Radix Sort for Negative Integers

Question

I am trying to implement radix sort for integers, including negative integers. For non-negative ints, I was planning to create a queue of 10 queues correspondingly for the digits 0-9 and implement the LSD algorithm. But I was kind of confused with negative integers. What I am thinking now, is to go ahead and create another queue of 10 queues for them and separately sort them and then at the end, I will gave 2 lists, one containing negative ints sorted and the other containing non-negative ints. And finally I would merge them.

What do you think about this? Is there more efficient way to handle with negative integers?

Thank you!

Answer 1

Probably the easiest way to handle signed values is to offset the starting position for the accumulation (i.e., generation of positional offsets) when operating on the most significant digit. Transforming the input so all digits may be treated as unsigned is also an option, but requires applying an operation over the value array at least twice (once to prepare input and again to restore output).

This uses the first technique as well as byte-sized digits (byte access is generally more efficient):

void lsdradixsort(int* a, size_t n)
{
    // isolate integer byte by index.
    auto bmask = [](int x, size_t i)
    {
        return (static_cast<unsigned int>(x) >> i*8) & 0xFF;
    };

    // allocate temporary buffer.
    auto m = std::make_unique<int[]>(n);
    int* b = m.get();

    // for each byte in integer (assuming 4-byte int).
    for ( size_t i, j = 0; j < 4; j++ ) {
        // initialize counter to zero;
        size_t h[256] = {}, start;

        // histogram.
        // count each occurrence of indexed-byte value.
        for ( i = 0; i < n; i++ )
            h[bmask(a[i], j)]++;

        // accumulate.
        // generate positional offsets. adjust starting point
        // if most significant digit.
        start = (j != 3) ? 0 : 128;
        for ( i = 1+start; i < 256+start; i++ )
            h[i % 256] += h[(i-1) % 256];

        // distribute.
        // stable reordering of elements. backward to avoid shifting
        // the counter array.
        for ( i = n; i > 0; i-- )
            b[--h[bmask(a[i-1], j)]] = a[i-1];
        std::swap(a, b);
    }
}

Note: Code is untested. Apologies for any errors/typos.

Answer 2

The accepted answer requires one more pass than necessary.

Just flip the sign bit.

This is essentially the answer posted by punpcklbw, but there is a tiny caveat that needs to be addressed. Specifically, this assumes you are working with a two's-complement representation, which is true for 99.999% of us. For example, both Java and Rust specify that signed integers use two's-complement. The C and C++ specs don't require any specific format, but neither MSVC, GCC, nor LLVM support other representations. In assembly, almost any CPU you will deal with is two's-complement, and you will surely already know otherwise.

The following table demonstrates that simply flipping the sign bit will cause two's-complement integers to sort correctly when sorted lexicographically. The first column gives a binary value, the second column gives the interpretation of those bits as 4-bit signed integers, and the third column gives the interpretation of those bits with the high bit flipped.

Binary    | 2s-comp  | Flip sign
----------+----------+----------
0000      | 00       | -8
0001      | +1       | -7
0010      | +2       | -6
0011      | +3       | -5
0100      | +4       | -4
0101      | +5       | -3
0110      | +6       | -2
0111      | +7       | -1
1000      | -8       | 00
1001      | -7       | +1
1010      | -6       | +2
1011      | -5       | +3
1100      | -4       | +4
1101      | -3       | +5
1110      | -2       | +6
1111      | -1       | +7

The answer given by punpcklbw recommends only flipping the bit when you're looking at the highest byte, but my gut tells me that it would be faster to simply flip the top bit every time before you pull out the byte you're looking at. That's because doing a single xor every time to flip the bit will be faster than doing a branch every time to decide if you should flip or not.

[An important detail to mention, which some textbooks fail to address properly, is that a real implementation should sort by byte, not by decimal digit. This is obviously still correct, because you're just sorting by a radix of 256 instead of 10, but thinking about it this way will lead to better implementations.]