Radix sort is a non-comparison sorting algorithm that works by sorting numbers digit by digit, starting from the least significant digit to the most significant digit. Let's see how it works with this example array containing numbers like 170, 45, 75, 90, 2, 802, 24, and 66. Unlike comparison-based algorithms, radix sort processes digits systematically and is particularly efficient for sorting integers.
Let's understand how radix sort works step by step. First, we find the maximum number to determine how many digits we need to process. Then, for each digit position starting from the rightmost, we extract that digit from each number and sort them into buckets labeled 0 through 9. For example, with number 802, the units digit is 2, tens digit is 0, and hundreds digit is 8. After sorting into buckets, we collect the numbers in order. This process is repeated for each digit position.
In the first step, we sort by the units digit. We extract the rightmost digit from each number: 170 ends in 0, 45 ends in 5, 75 ends in 5, 90 ends in 0, 2 ends in 2, 802 ends in 2, 24 ends in 4, and 66 ends in 6. We place each number into the corresponding bucket based on their units digit. Then we collect all numbers from the buckets in order from 0 to 9, giving us a partially sorted array.
In the second step, we sort by the tens digit. From our partially sorted array, we extract the tens digit: 170 has tens digit 7, 90 has 9, 2 has 0, 802 has 0, 24 has 2, 45 has 4, 75 has 7, and 66 has 6. Notice that 2 is treated as having 0 in the tens position. After distributing into buckets and collecting them in order, we get another intermediate result.
In the final step, we sort by the hundreds digit. Most numbers have 0 in the hundreds position, 170 has 1, and 802 has 8. After the final distribution and collection, we get our completely sorted array: 2, 24, 45, 66, 75, 90, 170, 802. Radix sort has linear time complexity O(d times n) where d is the number of digits and n is the array size, making it very efficient for sorting integers with a fixed number of digits.
The first step in radix sort is to determine how many digit positions we need to process. We do this by finding the maximum number in the array and counting its digits. In our example array, the maximum number is 802. We convert it to a string '802' and get its length, which is 3. This means we need exactly 3 iterations: one for the units digit, one for the tens digit, and one for the hundreds digit.
Before we start sorting, we need to set up our bucket system. We create 10 empty buckets, one for each possible digit from 0 to 9. Each bucket is initially empty and will temporarily hold numbers based on the digit we're currently examining. For example, when sorting by units digit, all numbers ending in 0 go to bucket 0, numbers ending in 1 go to bucket 1, and so on. After distributing all numbers, we collect them from the buckets in order from 0 to 9.