MSD radix sort

Cost and properties

time	sublinear in the input
examines	just enough characters
needs	aux array + R counters per call
variable length	handled

Reference: Sedgewick & Wayne, §5.1.

MSD radix sort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def msd_sort(a):
    aux = [None] * len(a)
    _msd(a, aux, 0, len(a) - 1, 0)
    return a

# R is the RADIX -- the alphabet size. 26 here because the keys are
# lowercase words, so a letter's digit is ord(c) - ord('a'), and -1 means
# 'past the end of the key' (which must sort before every real letter).
# Use 256 and ord(s[d]) for arbitrary bytes; the algorithm is unchanged.
def _char_at(s, d):                       # -1 past the end of the string
    return -1 if d >= len(s) else ord(s[d]) - ord('a')

def _msd(a, aux, lo, hi, d):
    if hi <= lo:
        return                            # 0 or 1 keys: nothing to do
    R = 26
    count = [0] * (R + 2)                 # +2: one slot for 'end of key'
    for i in range(lo, hi + 1):
        count[_char_at(a[i], d) + 2] += 1
    for r in range(R + 1):
        count[r + 1] += count[r]
    for i in range(lo, hi + 1):
        aux[count[_char_at(a[i], d) + 1]] = a[i]
        count[_char_at(a[i], d) + 1] += 1
    for i in range(lo, hi + 1):
        a[i] = aux[i - lo]
    for r in range(R):                    # recur inside each character group
        _msd(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1)

Why it works

Sublinear, genuinely

MSD examines just enough characters to distinguish the keys. On random input from a large alphabet that is about log_R n characters per key — so it can sort without reading most of the input. On the distinct first letters preset it finishes after one character each. LSD, by contrast, always reads every character of every key.

The end-of-string slot

_char_at returns −1 past the end of a key, and the counts are offset by 2 rather than 1 to leave room for it. Keys that have run out therefore sort before every real character — which is exactly right (pre precedes prefix) and is what lets MSD handle variable-length keys at all.

The performance trap

Every recursive call allocates R+2 counters. With R = 256 and many tiny subarrays, that initialisation dwarfs the sorting: MSD can be slower than insertion sort on small groups, and for a large alphabet like Unicode it is much worse. Real implementations cut off to insertion sort for subarrays under ~15 keys, and that cutoff is not an optimisation — without it MSD is unusable.

Or use 3-way string quicksort

Sedgewick and Bentley's 3-way string quicksort partitions on a single character into <, =, > — no counters, in place, and it handles long shared prefixes well. It is the standard choice when keys have structure, and it is what the course recommends over MSD in practice.

What to try in the animation

Unlike LSD, keys may have different lengths, and the sort stops looking at a key as soon as it is distinguished from the others.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• seashells (course) — she sells seashells by the sea shore
• long shared prefixes — prefix prefixes prefixed pre prefer press
• distinct first letters — zebra apple mango kiwi banana
• mixed lengths — a ab abc b ba bca c

Open MSD radix sort in the player →

The rest of Radix sorts

• Key-indexed counting Count how many keys have each value, turn the counts into starting positions, then place…
• LSD radix sort Sort by the last character, then the one before it, and so on.