Counting Sort in Radix Sort

Radix sort performs a counting sort for each place digit present in the list. There are numbers in the list that have a value in the one’s place, the ten’s place, and the hundred’s place — therefore, there is a maximum of three places of digits that radix sort must sort using the counting sort subroutine.

Another way to think about this is:

$104$ is the largest number in the list, therefore, $104$ is the $k$ value. To determine the number of digits needed to represent $k$ (and therefore, all the numbers less than $k$ ), use the following formula: $d = \lfloor(\log_b(k) +1)\rfloor$ . Plugging in, we get $d = \lfloor(\log_{10}(104) +1)\rfloor = 3$ .