Radix Sort makes several passes of the previous Counting Sort in order to completely sort integer keys. Counting Sort can be used as the intermediate sorting routine because it provides a stable sort. Let the n integer keys fall in the range , and . Then we need passes of Counting Sort; each pass works on r-bit blocks of the input keys, starting from the least significant block of r bits to the most significant block. Therefore, the overall complexity of Radix Sort is exactly times that of Counting Sort. We choose the radix R to be (note that we are assuming ), and a typical value is R=1024. Assuming that M is polynomial in n, becomes a constant, and therefore, the total complexity reduces to . Thus, the computational analysis derived for radix sort is asymptotically optimal since sequential radix sort runs in whenever the range of integers is polynomial in n. The lower bound for communication is since each processor might need to inject all of its elements into the network, and the communication complexity is asymptotically optimal whenever .