Radix Sort

LSD (Least Significant Digit first):
  Sort by units digit, then tens, then hundreds, ...
  Simpler to implement; produces correct result because
  each pass is stable (preserves order from previous pass).

MSD (Most Significant Digit first):
  Sort by highest digit first, then recursively sort each bucket.
  More complex; natural fit for strings and variable-length keys.
  Used in string sorting (e.g. MSD radix sort for string arrays).

For integers: LSD is the standard choice.

def counting_sort_by_digit(arr, exp):
    """Stable sort by the digit at position exp (1, 10, 100, ...)."""
    n      = len(arr)
    output = [0] * n
    count  = [0] * 10        # digits 0–9

    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1

    for i in range(1, 10):   # prefix sums
        count[i] += count[i - 1]

    for num in reversed(arr):    # right-to-left for stability
        digit = (num // exp) % 10
        count[digit] -= 1
        output[count[digit]] = num

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

nums = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(nums))   # [2, 24, 45, 66, 75, 90, 170, 802]

Input: [170, 45, 75, 90, 802, 24, 2, 66]

Pass 1 — sort by units digit (exp=1):
  digits: 0, 5, 5, 0, 2, 4, 2, 6
  → [170, 90, 802, 2, 24, 45, 75, 66]

Pass 2 — sort by tens digit (exp=10):
  digits: 7, 9, 0, 0, 2, 4, 7, 6
  → [802, 2, 24, 45, 66, 170, 75, 90]

Pass 3 — sort by hundreds digit (exp=100):
  digits: 8, 0, 0, 0, 0, 1, 0, 0
  → [2, 24, 45, 66, 75, 90, 170, 802]

# Radix sort is O(nk) where k = number of digits
# For 32-bit integers: k=10 decimal digits (or 32 binary digits)
# So k is effectively constant → O(n) for fixed-width integers

# Best use cases:
# - Sorting large arrays of integers with bounded values
# - Sorting fixed-length strings (treat each character as a digit)
# - Situations where O(n log n) comparison sort is a bottleneck

# Not suitable for:
# - Floating-point numbers (need special handling)
# - Variable-length strings (MSD required)
# - When n is small (overhead of multiple passes outweighs O(n log n))

# Comparison with counting sort:
# Counting sort: O(n+k) where k = max VALUE (can be huge)
# Radix sort:    O(n*d) where d = number of digits (typically 10–32)
# Radix sort handles larger values without blowing up space.