# Radix Exchange Sort

# Radix Exchange Sort

Radix exchange sort is an in place radix sorting algorithm for binary keys, usually integers. It processes bits from most significant to least significant and partitions the array into two regions at each bit.

At each step, all keys with bit 0 move before all keys with bit 1. The algorithm then recursively sorts both regions using the next bit.

## Problem

Given an array $A$ of nonnegative integers, sort it in increasing order by examining binary digits.

Each key can be written as:

$$
x = b_{m-1}b_{m-2}\cdots b_1b_0
$$

where each bit satisfies:

$$
b_i \in {0, 1}
$$

## Idea

The most significant bit determines the largest scale ordering. Keys with a 0 in that bit must come before keys with a 1 in that bit. After this partition is correct, each side can be sorted independently by the next bit.

This is the radix analogue of quicksort partitioning, but the pivot is a bit position rather than a chosen key.

## Algorithm

```text id="r4x8ke"
radix_exchange_sort(A, lo, hi, bit):
    if hi - lo <= 1 or bit < 0:
        return

    i = lo
    j = hi - 1

    while i <= j:
        while i <= j and bit_at(A[i], bit) == 0:
            i += 1

        while i <= j and bit_at(A[j], bit) == 1:
            j -= 1

        if i < j:
            swap A[i], A[j]
            i += 1
            j -= 1

    radix_exchange_sort(A, lo, i, bit - 1)
    radix_exchange_sort(A, i, hi, bit - 1)
```

## Example

Sort:

$$
A = [5, 3, 7, 1]
$$

Using 3 bit binary form:

| value | bits |
| ----- | ---- |
| 5     | 101  |
| 3     | 011  |
| 7     | 111  |
| 1     | 001  |

First partition by bit 2:

| bit 2 | values |
| ----- | ------ |
| 0     | 3, 1   |
| 1     | 5, 7   |

Then recursively sort each side by bit 1 and bit 0.

Final result:

$$
[1, 3, 5, 7]
$$

## Correctness

At a call on bit $b$, the partition step places every key with bit $0$ before every key with bit $1$. Since higher bits have already been fixed by previous recursive calls, the current bit is the next deciding bit.

The recursive calls sort each partition by all remaining lower bits. Therefore, after recursion finishes, each partition is sorted, and all elements in the left partition are smaller than all elements in the right partition.

By induction on the bit position, the whole array is sorted.

## Complexity

Let:

* $n$ be the number of elements
* $m$ be the number of bits examined

Each level scans its active subarrays once. Across one bit level, the total work is $O(n)$.

Time:

$$
O(nm)
$$

For fixed width integers, $m$ is constant, so the running time is linear in $n$.

Auxiliary space:

$$
O(m)
$$

for recursion stack space.

## Properties

| property         | value |
| ---------------- | ----- |
| stable           | no    |
| in place         | yes   |
| comparison based | no    |
| direction        | MSD   |
| radix            | 2     |

## When to Use

Use radix exchange sort when sorting fixed width nonnegative integers and in place operation matters. It is simple, allocation-light, and based only on bit tests and swaps.

Avoid it when stability is required, when signed integer ordering needs special handling, or when a tuned bytewise radix sort is available and memory for an auxiliary array is acceptable.

## Implementation

```python id="u8r2nx"
def radix_exchange_sort(a):
    if len(a) <= 1:
        return a

    max_bit = max(a).bit_length() - 1

    def bit_at(x, bit):
        return (x >> bit) & 1

    def sort(lo, hi, bit):
        if hi - lo <= 1 or bit < 0:
            return

        i = lo
        j = hi - 1

        while i <= j:
            while i <= j and bit_at(a[i], bit) == 0:
                i += 1

            while i <= j and bit_at(a[j], bit) == 1:
                j -= 1

            if i < j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1

        sort(lo, i, bit - 1)
        sort(i, hi, bit - 1)

    sort(0, len(a), max_bit)
    return a
```