# Word Radix Sort

# Word Radix Sort

Word radix sort is a radix sorting method specialized for fixed width machine words such as 32 bit or 64 bit integers. It processes keys a byte or group of bits at a time using fast bit operations.

This approach matches hardware representation and is widely used in high performance systems.

## Problem

Given an array $A$ of $n$ fixed width integers, sort the array efficiently.

Each key is a word of $w$ bits, often:

* 32 bit integers
* 64 bit integers

## Idea

Partition keys based on chunks of bits. A common choice is to process one byte at a time, so the base is:

$$
b = 2^8 = 256
$$

Each key is decomposed into:

$$
x = d_{m-1} d_{m-2} \cdots d_1 d_0
$$

where each digit is one byte.

Then perform LSD or MSD radix sorting over these digits.

## Algorithm (LSD Bytewise)

```text id="m5k8pa"
word_radix_sort(A):
    bytes = word_size_in_bytes

    for p from 0 to bytes - 1:
        stable_counting_sort_by_byte(A, p)

    return A
```

## Byte Extraction

For byte position $p$:

$$
d_p = (x >> (8p)) \mathbin{\&} 255
$$

## Example

Sort:

$$
[305419896, 2596069104, 267242409, 2271560481]
$$

Using 32 bit words, process 4 bytes from least significant to most significant.

After all passes, the array is sorted.

## Signed Integers

For signed integers, direct radix sorting needs adjustment because negative values have high bits set.

A common fix:

* reinterpret integers as unsigned
* or shift values:

$$
x' = x - \min
$$

Alternatively, modify the final pass to treat the most significant byte with signed ordering.

## Correctness

Each pass groups keys by the current byte. Stability ensures that ordering of lower bytes is preserved. After processing all bytes, keys are sorted by all bits.

## Complexity

Let:

* $n$ be number of elements
* $m$ be number of bytes

Each pass costs:

$$
O(n + 256)
$$

Total:

$$
O(n \cdot m)
$$

For 64 bit integers, $m = 8$, so the runtime is linear in $n$.

Space:

$$
O(n + 256)
$$

## Properties

| property         | value  |
| ---------------- | ------ |
| stable           | yes    |
| in place         | no     |
| comparison based | no     |
| radix            | $2^8$  |
| typical passes   | 4 or 8 |

## When to Use

Use word radix sort when:

* sorting large arrays of integers
* fixed width representation is available
* high throughput is required
* comparison sorting is too slow

Avoid when:

* keys are not fixed width
* stability is not needed and memory is constrained
* data is very small

## Implementation (Python)

```python id="t3k7qa"
def word_radix_sort(a):
    if not a:
        return a

    max_bits = max(a).bit_length()
    bytes_count = (max_bits + 7) // 8

    for p in range(bytes_count):
        count = [0] * 256

        for x in a:
            byte = (x >> (8 * p)) & 255
            count[byte] += 1

        for i in range(1, 256):
            count[i] += count[i - 1]

        out = [0] * len(a)

        for i in range(len(a) - 1, -1, -1):
            x = a[i]
            byte = (x >> (8 * p)) & 255
            count[byte] -= 1
            out[count[byte]] = x

        a = out

    return a
```