So how does a radix sort use this base numbering system to sort integers? First, there are two different kinds of radix sort: most significant digit, or MSD, and least significant digit, or LSD.
Both radix sorts organize the input list into ten “buckets”, one for each digit. The numbers are placed into the buckets based on the MSD (left-most digit) or LSD (right-most digit). For example, the number 2367 would be placed into the bucket “2” for MSD and into “7” for LSD.
This bucketing process is repeated over and over again until all digits in the longest number have been considered. The order within buckets for each iteration is preserved. For example, the numbers 23, 25 and 126 are placed in the “3”, “5”, and “6” buckets for an initial LSD bucketing. On the second iteration of the algorithm, they are all placed into the “2” bucket, but the order is preserved as
23, 25, 126.
A sample LSD radix sort is shown to the left (empty buckets for each step are hidden). Why do we bucket the shorter numbers into the “0” bucket on the last step?