Pseudo Code

countingSortByDigit(array, exp):
   n = length(array)
   output = array of size n
   count = array of 10 zeros
   for each x in array:                 # 各桁をカウント
      count[(x / exp) % 10] += 1
   for d from 1 to 9:                   # 累積和を計算 -> 配置位置の決定
      count[d] += count[d - 1]
   for k from n-1 down to 0:            # 後ろから配置（安定性を維持）
      d = (array[k] / exp) % 10
      count[d] -= 1
      output[count[d]] = array[k]
   return output

radixSort(array):
   max = largest value in array
   exp = 1
   while max / exp > 0:
      array = countingSortByDigit(array, exp)
      exp = exp * 10