## Algorithm

```for i = 1 to d do stable-sort A on ith from right```

## Complexity

Since we use counting sort, the time is $\Theta \left(d\left(n+r\right)\right)$ or $\Theta \left({log}_{r}s\left(n+r\right)\right)$.

Proposition. The optimal radix is $\frac{n}{lnn}$.
• $\frac{d}{dr}{log}_{r}s\left(n+r\right)=0$
• $r\approx \frac{n}{ln}r$
• $r=\frac{n}{lnn}$
This produces the optimal running time: $\Theta \left(\frac{nlogs}{logn}\right)$.