Radix Sort for Strings

Radix Sort for strings extends the classic digit-based Radix Sort idea to characters. Instead of processing numeric digits from least significant to most significant, the algorithm processes string characters, usually from the last character to the first (LSD - Least Significant Digit approach) or from the first to the last (MSD - Most Significant Digit approach).

How It Works

Each string is treated as a sequence of characters. Strings are padded to equal length using a placeholder character that sorts before all valid characters. The algorithm performs a stable counting sort pass on each character position, working right to left for LSD radix sort.

Algorithm Steps (LSD Radix Sort)

• Find the length of the longest string, pad shorter strings.
• Starting from the last character position, perform a stable counting sort on that position across all strings.
• Move to the previous character position and repeat.
• After processing the first character position, the strings are fully sorted.

def radix_sort_strings(arr):
    max_len = max(len(s) for s in arr)
    arr = [s.ljust(max_len, chr(0)) for s in arr]

    for pos in range(max_len - 1, -1, -1):
        buckets = [[] for _ in range(257)]
        for s in arr:
            buckets[ord(s[pos])].append(s)
        arr = [s for bucket in buckets for s in bucket]

    return [s.rstrip(chr(0)) for s in arr]

Complexity

Here n is the number of strings and k is the maximum string length. Because Radix Sort avoids character-by-character comparisons across the whole string at once, it can outperform comparison-based sorts like Quick Sort for large collections of fixed or bounded-length strings.

Applications

• Sorting large dictionaries or word lists.
• Sorting fixed-length identifiers such as postal codes or product SKUs.
• Used internally in suffix array construction for string processing.