Radix Sort

Algorithm

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

Complexity

Since we use counting sort, the time is Θ(d(n+r)) or Θ(logrs(n+r)).

Optimal radix

Proposition. The optimal radix is nlnn.

Proof. Use differentiation to optimize:

This produces the optimal running time: Θ(nlogslogn).