# Least Significant Byte Sort

# 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

```text id="n3p8qx"
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

```python id="q2m7va"
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
```