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)

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)

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