Radix Sort

Sort digit-by-digit from least significant to most significant. Uses Counting Sort as a stable subroutine for each digit pass.

RADIX-SORT(A):
  maxVal = max(A)
  k = number of digits in maxVal

  FOR place = 1, 10, 100, ... (each digit position):
    COUNTING-SORT-BY-DIGIT(A, place)

COUNTING-SORT-BY-DIGIT(A, place):
  n = length(A)
  output = array of size n
  count  = array of size 10, all zeros

  // Count occurrences of each digit
  FOR i = 0 TO n-1:
    digit = (A[i] / place) % 10
    count[digit]++

  // Cumulative count
  FOR i = 1 TO 9:
    count[i] += count[i-1]

  // Build output (traverse right-to-left for stability)
  FOR i = n-1 DOWNTO 0:
    digit = (A[i] / place) % 10
    output[count[digit]-1] = A[i]
    count[digit]--

  COPY output INTO A