# MSD Radix Sort

# MSD Radix Sort

MSD radix sort processes digits from most significant to least significant. It partitions the array by the leading digit, then recursively sorts each partition.

This approach follows lexicographic order naturally and works well for strings and variable length keys.

## Problem

Given an array $A$ of $n$ keys, each represented as a sequence of digits or characters, sort them lexicographically.

A key can be written as:

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

MSD radix sort processes:

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

## Idea

At each step:

1. Group elements by current digit
2. Recursively sort each group by the next digit
3. Concatenate groups in order

## Algorithm

```text id="w5g8re"
msd_radix_sort(A, d, base):
    if len(A) <= 1:
        return A

    buckets = array of lists of size base

    for x in A:
        digit = get_digit(x, d)
        buckets[digit].append(x)

    result = empty list

    for i from 0 to base - 1:
        if buckets[i] not empty:
            sorted_bucket = msd_radix_sort(buckets[i], d + 1, base)
            append sorted_bucket to result

    return result
```

## Example

Sort strings:

$$
["dog", "cat", "apple", "car"]
$$

Step 1, group by first character:

* "a": ["apple"]
* "c": ["cat", "car"]
* "d": ["dog"]

Step 2, recursively sort each group:

* "apple" remains
* "cat", "car" sorted by next character
* "dog" remains

Final result:

$$
["apple", "car", "cat", "dog"]
$$

## Handling Variable Length Keys

For strings of different lengths, define a sentinel digit:

* shorter keys have a special value smaller than all valid digits
* this ensures correct lexicographic order

Example:

$$
"car" < "cart"
$$

## Correctness

At each level, elements are grouped by the current digit. All elements in a group share the same prefix. Recursive sorting orders them by remaining suffix. Concatenation of groups yields full lexicographic order.

## Complexity

Let:

* $n$ be number of keys
* $m$ be average key length
* $b$ be base

Time:

$$
O(n \cdot m)
$$

in typical cases

Worst case may degrade when many keys share long common prefixes.

Space:

$$
O(n + b \cdot m)
$$

due to recursion and bucket storage

## When to Use

Use MSD radix sort when:

* sorting strings or variable length keys
* lexicographic order is required
* keys share common prefixes
* recursive partitioning improves locality

Avoid when recursion overhead is high or when keys are fixed width integers where LSD is simpler.

## Implementation

```python id="h2k8vm"
def msd_radix_sort(a, d=0):
    if len(a) <= 1:
        return a

    buckets = {}

    for s in a:
        key = s[d] if d < len(s) else ""
        buckets.setdefault(key, []).append(s)

    result = []

    for key in sorted(buckets.keys()):
        result.extend(msd_radix_sort(buckets[key], d + 1))

    return result
```