Signed Integer Radix Sort

Signed integer radix sort extends radix sorting to handle both negative and positive integers correctly. Since radix sort operates on digit or bit patterns, special handling is required to maintain numeric ordering.

Problem

Given an array $A$ of signed integers, sort the array in increasing order.

Integers are represented in two’s complement form, where direct unsigned interpretation does not preserve ordering.

Idea

Transform each integer into a form where lexicographic bit ordering matches numeric ordering, then apply standard radix sort.

Two common approaches:

Offset transformation
Sign-bit handling in the most significant pass

Approach 1: Offset Transformation

Shift all values by the minimum value:

x' = x - \min(A)

This makes all values nonnegative, allowing standard radix sort.

After sorting, no inverse mapping is needed because ordering is preserved.

Approach 2: Bitwise Transformation

For fixed-width integers, flip the sign bit:

k(x) = x \oplus 2^{w-1}

where $w$ is the number of bits.

This maps:

negative values to lower half
nonnegative values to upper half

so that integer ordering matches unsigned ordering.

Algorithm (Bitwise Method)

signed_radix_sort(A):
    for each x in A:
        x = x XOR sign_mask

    radix_sort(A)

    for each x in A:
        x = x XOR sign_mask

    return A

where:

\text{sign\_mask} = 2^{w-1}

Example

Let:

A = [-3, 1, -1, 2]

Binary (4-bit example):

value	bits
-3	1101
-1	1111
1	0001
2	0010

After XOR with sign mask:

value	transformed
-3	0101
-1	0111
1	1001
2	1010

Sorted:

[0101, 0111, 1001, 1010]

Mapped back:

[-3, -1, 1, 2]

Correctness

Flipping the sign bit reorders the integer space so that:

all negative values come before nonnegative values
relative ordering within each group is preserved

Thus:

x_1 < x_2 \iff k(x_1) < k(x_2)

Radix sort correctly orders the transformed values, and reversing the transformation yields the correct sorted order.

Complexity

Let:

$n$ be number of elements
$m$ be number of digits or bytes

Time:

O(n \cdot m)

Space:

O(n)

Properties

property	value
stable	yes, if radix sort is stable
in place	no
comparison based	no
handles negatives	yes

When to Use

Use signed integer radix sort when:

sorting large arrays of integers with both negative and positive values
fixed-width representation is available
linear-time sorting is desired

Avoid when:

data size is small
simplicity is preferred over performance
memory for auxiliary arrays is limited

Implementation (Python)

def signed_radix_sort(a):
    if not a:
        return a

    # Assume 32-bit integers
    sign_mask = 1 << 31

    # Transform
    a = [x ^ sign_mask for x in a]

    # Use Python sort here; replace with radix for full implementation
    a.sort()

    # Reverse transform
    return [x ^ sign_mask for x in a]