# Binary Radix Sort

# Binary Radix Sort

Binary radix sort sorts integers by examining their binary representation bit by bit. Instead of using counting arrays, it partitions elements into two groups based on whether a bit is 0 or 1.

This yields a simple and memory efficient radix sort specialized for base 2.

## Problem

Given an array $A$ of integers, sort them in increasing order using their binary representation.

Each number can be written as:

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

where each bit satisfies:

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

## Idea

At each bit position:

* separate elements with bit 0 and bit 1
* maintain stability or partition in place
* repeat for all bit positions

Two main approaches exist:

* LSD style using stable partition
* MSD style using recursive partition

## Algorithm (LSD Stable)

```text id="b7m2qs"
binary_radix_sort(A, bits):
    for p from 0 to bits - 1:
        stable_partition A by bit p
    return A
```

The stable partition ensures that ordering from previous passes is preserved.

## Algorithm (MSD In Place)

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

    i = lo
    j = hi - 1

    while i <= j:
        if bit(A[i]) == 0:
            i += 1
        else:
            swap A[i], A[j]
            j -= 1

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

## Example

Sort:

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

Binary:

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

After sorting by least significant bit:

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

After next bit:

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

After most significant bit:

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

## Correctness

Each pass partitions elements by the current bit. In the LSD version, stability ensures that lower bits remain ordered. In the MSD version, recursive partitioning ensures that higher bits dominate ordering.

After processing all bits, the array is ordered by full binary value.

## Complexity

Let:

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

Time:

$$
O(n \cdot m)
$$

Space:

* LSD stable version: $O(n)$
* MSD in place version: $O(1)$ auxiliary

## Properties

| property         | value    |
| ---------------- | -------- |
| base             | 2        |
| stable           | optional |
| in place         | possible |
| comparison based | no       |

## When to Use

Use binary radix sort when:

* sorting integers with fixed bit width
* memory must be minimal
* simple partition logic is preferred
* hardware level bit operations are efficient

It is often used in low level systems and performance critical pipelines.

## Implementation (Python, MSD)

```python id="u3k9pz"
def binary_radix_sort(a):
    max_bits = max(a).bit_length()

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

        i, j = lo, hi - 1

        while i <= j:
            if ((a[i] >> bit) & 1) == 0:
                i += 1
            else:
                a[i], a[j] = a[j], a[i]
                j -= 1

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

    sort(0, len(a), max_bits - 1)
    return a
```