Least Significant Byte Sort

Least Significant Byte sort is the byte oriented version of LSD radix sort. It processes fixed width keys one byte at a time, starting from the least significant byte and moving toward the most significant byte.

It relies on a stable inner sorting step, usually counting sort with 256 buckets.

Problem

Given an array $A$ of fixed width integer keys, sort the array in increasing order.

Each key can be written as:

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

where each $d_i$ is a byte:

0 \le d_i < 256

Idea

Sort the array by byte positions in increasing order of significance:

d_0, d_1, \ldots, d_{m-1}

After each pass, the array is sorted by the processed suffix of bytes.

Algorithm

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

    return A

Byte extraction:

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

Example

Sort:

A = [513, 256, 258, 1]

Byte form:

value	high byte	low byte
513	2	1
256	1	0
258	1	2
1	0	1

After sorting by low byte:

[256, 513, 1, 258]

After sorting by high byte:

[1, 256, 258, 513]

Correctness

After processing byte $p$ , the array is sorted by the suffix:

d_p d_{p-1}\cdots d_0

The base case holds after sorting by $d_0$ . For the inductive step, stable sorting by $d_p$ orders elements by the new byte while preserving the ordering of lower bytes.

After all bytes have been processed, the array is sorted by the full key.

Complexity

Let:

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

Each pass costs:

O(n + 256)

Total time:

O(m(n + 256))

Space:

O(n + 256)

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

Properties

property	value
stable	yes
in place	no
comparison based	no
direction	LSD
radix	256

When to Use

Use LSB sort when:

sorting large arrays of fixed width integers
stability is required
byte extraction is cheap
auxiliary memory is acceptable

Avoid when:

memory must be minimal
keys are variable length
recursive MSD methods perform better on the dataset

Implementation

def lsb_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:
            b = (x >> (8 * p)) & 255
            count[b] += 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]
            b = (x >> (8 * p)) & 255
            count[b] -= 1
            out[count[b]] = x

        a = out

    return a