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 
.