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)

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)

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)

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