Sort numbers one digit at a time, from the least significant digit to the most, using a stable counting sort for each digit. Because every pass is stable, the order from earlier digits survives as the tie-breaker.
- Average time
- O(d·(n + b))
- Space
- O(n + b)