# Signed Integer Radix Sort

# 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:

1. **Offset transformation**
2. **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)

```text id="s4k9qx"
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)

```python id="m8q2zp"
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]
```