LSD radix sort

Cost and properties

time	O(w · n) — w = key length
compares	zero
needs	fixed-length keys
classic use	punched-card sorters

Reference: Sedgewick & Wayne, §5.1; Hollerith 1887.

LSD 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 lsd_sort(a, w):
    # a is a list of w-character strings. Key-indexed counting on
    # character d, for d = w-1 down to 0. It works ONLY because each pass
    # is stable: earlier passes' order survives inside equal characters.
    # 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'). Use 256
    # and ord(c) for arbitrary bytes; nothing else about the code changes.
    R, n, A = 26, len(a), ord('a')
    aux = [None] * n
    for d in range(w - 1, -1, -1):        # RIGHT to LEFT
        count = [0] * (R + 1)
        for i in range(n):
            count[ord(a[i][d]) - A + 1] += 1
        for r in range(R):
            count[r + 1] += count[r]
        for i in range(n):
            aux[count[ord(a[i][d]) - A]] = a[i]
            count[ord(a[i][d]) - A] += 1
        for i in range(n):
            a[i] = aux[i]
    return a

Why it works

Why right to left

The last pass sorts on the most significant character, so it decides the overall order. Within a group of keys that agree on that character, the order left behind by the previous pass survives — because each pass is stable — and that order was correct for the remaining characters. Induct backwards and the whole thing is sorted after w passes.

Do it left to right with the same code and it is simply wrong: the later passes destroy the earlier work. Left-to-right requires recursion into groups, which is MSD.

The cost

w passes over n keys: O(w·n) — linear in the total input size, and independent of how the keys are arranged. For 7-character licence plates that is 7 passes no matter how many million plates you have, beating n log n comfortably. Note it examines every character of every key, even when the first one already decides the answer.

Punched cards

This algorithm predates computers. Hollerith's card sorters (1887 census) worked exactly this way: a mechanical sorter distributed cards into bins by one column, the operator stacked the bins in order, and repeated for the next column to the left. “Stacking the bins in order” is stability, implemented in cardboard.

Limitations

Keys must be the same length — real implementations pad, or switch to MSD for variable-length strings. And R counters are allocated per pass, so for a large alphabet with few keys the R term dominates. It is also not in place: aux is the same size as the input.

What to try in the animation

All keys must have the same length. The default is the course's 3-character example; the licence-plate preset is the historical use case.

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.

• 3-letter words (course) — dab add cab fad fee bad dad bee fed bed ebb ace
• licence plates — 4PGC938 2IYE230 3CI0720 1ICK750 1OHV845 4JZY524 1ICK750 3CI0720
• binary keys — 110 011 001 111 000 101 010 100
• same last character — axx bxx cxx dxx

Open LSD 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…
• MSD radix sort Sort on the first character, then recur inside each group.