Knuth provides the solution to this problem in his third volume of The Art of Computer Programming. Assume that we want to represent numbers in the range of 0..9999. Also assume that N=100 and n 2 =10000. We can sort the array using only two passes, if we increase the number of buckets to N. On the first pass we sort the array on the least significant digit (K mod n 2 ); on the second we sort the most significant digit. For example, if our array contained 9998, 452, and 4508, the first pass would place 9998 in the 98 bucket, 452 in the 52 bucket and 08 in the 08 bucket. The second pass would place 9998 in the 99 bucket, 452 in the 4 bucket and 4508 in the 45 bucket. Thus, we can decrease time by increasing the radix.