Radix Sort

Radix sort is a non-comparative integer sorting algorithm. Its core idea is to cut integers into different digits based on their place values, and then sort each digit separately. Radix sort can be implemented using either the Least Significant Digit (LSD) first method or the Most Significant Digit (MSD) first method, with LSD being more commonly used.

Detailed Process of Radix Sort

1. Algorithm Principle

   • Radix sort achieves sorting through multiple distribution and collection processes. For integers, the range of each digit is 0-9, so 10 buckets (queues or linked lists) are typically used to temporarily store data.
   • The LSD method starts sorting from the least significant digit and proceeds to the most significant digit; the MSD method does the opposite. LSD ensures sorting stability and is simpler to implement.

2. Specific Steps

   • Step 1: Determine the number of digits of the largest number
     First, traverse the array to find the maximum value and calculate its number of digits (e.g., if the maximum is 789, the number of digits is 3). This determines the number of sorting rounds.

     • Example array: [170, 45, 75, 90, 2, 802, 24, 66]
     • Maximum value: 802 → Number of digits: 3

   • Step 2: Perform distribution and collection by digit (LSD)
     Starting from the least significant digit (units place) to the most significant digit (hundreds place), each round distributes elements into buckets 0-9 based on the value of the current digit, and then collects them back into the array in order.

     • Round 1 (units place):
       • Distribution: Place elements into buckets based on the units digit.
         • Bucket 0: 170, 90
         • Bucket 2: 2, 802
         • Bucket 4: 24
         • Bucket 5: 45, 75
         • Bucket 6: 66
         • Other buckets are empty.
       • Collection: Retrieve elements in order from buckets 0-9 → [170, 90, 2, 802, 24, 45, 75, 66]
     • Round 2 (tens place):
       • Distribution: Place elements into buckets based on the tens digit (note: the tens digit of 2 is 0).
         • Bucket 0: 2, 802
         • Bucket 2: 24
         • Bucket 4: 45
         • Bucket 6: 66
         • Bucket 7: 170, 75
         • Bucket 9: 90
       • Collection: → [2, 802, 24, 45, 66, 170, 75, 90]
     • Round 3 (hundreds place):
       • Distribution: Place elements into buckets based on the hundreds digit (pad with 0 for numbers with fewer than three digits).
         • Bucket 0: 2, 24, 45, 66, 75, 90
         • Bucket 1: 170
         • Bucket 8: 802
       • Collection: → [2, 24, 45, 66, 75, 90, 170, 802] (sorted)

3. Algorithm Analysis

   • Time complexity: O(d·(n + k)), where d is the maximum number of digits, n is the number of elements, and k is the radix (usually k=10). When d is a constant, the complexity is linear O(n).
   • Space complexity: O(n + k), requiring additional bucket space.
   • Stability: Stable (the LSD method ensures that the order of identical key values remains unchanged).

4. Applicable Scenarios

   • Suitable for sorting integers or strings with a small range of digits.
   • If the maximum number of digits d is large, efficiency may be lower than comparative sorting algorithms (e.g., quicksort).

Through multiple rounds of digit-based sorting, radix sort avoids direct comparison of elements, thereby achieving sorting in linear time, but it relies on the digit representation of the data and stability.