Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It sorts numbers starting from the least significant digit (LSD) to the most significant digit (MSD). This method ensures that numbers are sorted correctly at each digit level before moving to the next. Radix Sort uses a stable sorting algorithm, typically Counting Sort, as a subroutine to sort digits.

The key idea is to sort the numbers digit by digit, ensuring that after each pass, the numbers are partially sorted based on the current digit. This process is repeated for each digit position, resulting in a fully sorted array. Radix Sort is particularly effective for sorting large numbers or fixed-length strings, where the number of digits (or characters) is constant.

Step-by-Step Algorithm

1. Find the Maximum Value in the Array

   • Traverse the array to find the maximum value.

     • It is used to determine the number of digits in the largest number, which dictates how many times we need to apply Counting Sort.

2. Process Each Digit Starting from the Rightmost

   • Radix Sort processes each digit position from the least significant to the most significant.
   • Start with the Rightmost Digit: Begin by sorting the array based on the rightmost digit (ones place) using Counting Sort. This is done by setting exp to 1.
   • Move Left Digit by Digit: Increase exp by multiplying it by 10 to move to the next digit to the left (tens place, hundreds place, etc.).
   • Repeat for All Digits: Continue this process until you've processed all digits of the largest number. Each time, the array gets sorted more accurately as you move leftward.

3. Counting Sort Based on Digit Position

   • Initialize Count Array:
     • Create a count array to store the frequency of digits (0-9).
     • Initialize the count array to zero.
   • Count Digit Occurrences:
     • Traverse the input array and count occurrences of each digit at the current digit position.
   • Cumulative Count:
     • Modify the count array to store cumulative counts.
     • This helps in determining the positions of the digits in the output array.
   • Build Output Array:
     • Traverse the input array in reverse order.
     • Place each number in the output array based on the current digit's position indicated by the count array.
     • Decrement the count for each digit after placing the number in the output array.
   • Copy to Original Array:
     • Copy the sorted output array back to the original array for the next iteration.

Algorithm Walkthrough

Input: array1 = [180, 55, 85, 90, 903, 243, 2, 6]

1. Find the Maximum Value

   • Maximum value = 903

2. Digit Position: Units (exp = 1)

   • Count Digit Occurrences:

     • Initialize count array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Counting digit occurrences:
       • For 180: digit = 0, count array becomes [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
       • For 55: digit = 5, count array becomes [1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
       • For 85: digit = 5, count array becomes [1, 0, 0, 0, 0, 2, 0, 0, 0, 0]
       • For 90: digit = 0, count array becomes [2, 0, 0, 0, 0, 2, 0, 0, 0, 0]
       • For 903: digit = 3, count array becomes [2, 0, 0, 1, 0, 2, 0, 0, 0, 0]
       • For 243: digit = 3, count array becomes [2, 0, 0, 2, 0, 2, 0, 0, 0, 0]
       • For 2: digit = 2, count array becomes [2, 0, 1, 2, 0, 2, 0, 0, 0, 0]
       • For 6: digit = 6, count array becomes [2, 0, 1, 2, 0, 2, 1, 0, 0, 0]

   • Cumulative Count:

     • Cumulative count array: [2, 2, 3, 5, 5, 7, 8, 8, 8, 8]

   • Build Output Array:

     • Traverse the input array in reverse order:
       • For 6: digit = 6, place 6 at index count[6]- 1 = 8 - 1 = 7.
         • Decrement count[6] by 1. count array becomes [2, 2, 3, 5, 5, 7, 7, 8, 8, 8].
         • output array becomes [0, 0, 0, 0, 0, 0, 0, 6].
       • For 2: digit = 2, place 2 at index count[2] - 1 = 3 - 1 = 2.
         • count array becomes [2, 2, 2, 5, 5, 7, 7, 8, 8, 8].
         • output array becomes [0, 0, 2, 0, 0, 0, 0, 6].
       • For 243: digit = 3, place 243 at index 4.
         • count array becomes [2, 2, 2, 4, 5, 7, 7, 8, 8, 8].
         • output array becomes [0, 0, 2, 0, 243, 0, 0, 6].
       • For 903: digit = 3, place 903 at index 3.
         • count array becomes [2, 2, 2, 3, 5, 7, 7, 8, 8, 8].
         • output array becomes [0, 0, 2, 903, 243, 0, 0, 6].
       • For 90: digit = 0, place 90 at index 1.
         • count array becomes [1, 2, 2, 3, 5, 7, 7, 8, 8, 8].
         • output array becomes [0, 90, 2, 903, 243, 0, 0, 6].
       • For 85: digit = 5, place 85 at index 6.
         • count array becomes [1, 2, 2, 3, 5, 6, 7, 8, 8, 8].
         • output array becomes [0, 90, 2, 903, 243, 0, 85, 6].
       • For 55: digit = 5, place 55 at index 5
         • count array becomes [1, 2, 2, 3, 5, 5, 7, 8, 8, 8].
         • output array becomes [0, 90, 2, 903, 243, 55, 85, 6].
       • For 180: digit = 0, place 180 at index 0.
         • count array becomes [0, 2, 2, 3, 5, 5, 7, 8, 8, 8].
         • output array becomes [180, 90, 2, 903, 243, 55, 85, 6].

   • Copy to Original Array:

     • array becomes [180, 90, 2, 903, 243, 55, 85, 6]

3. Digit Position: Tens (exp = 10)

   • Count Digit Occurrences:

     • Initialize count array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Counting digit occurrences:
       • count: [3, 0, 0, 0, 1, 1, 0, 0, 2, 1]`

   • Cumulative Count:

     • Cumulative count array: [3, 3, 3, 3, 4, 5, 5, 5, 7, 8]

   • Build Output Array:

     • Traverse the input array in reverse order:
       • For 6: digit = 0, place 6 at index 2.
         • count array becomes [2, 3, 3, 3, 4, 5, 5, 5, 7, 8].
         • output array becomes [0, 0, 6, 0, 0, 0, 0, 0]
       • For 85: digit = 8, place 85 at index 6.
         • count array becomes [2, 3, 3, 3, 4, 5, 5, 5, 6, 8].
         • output array becomes [0, 0, 6, 0, 0, 0, 85, 0]
       • For 55: digit = 5, place 55 at index 4.
         • count array becomes [2, 3, 3, 3, 4, 4, 5, 5, 6, 8].
         • output array becomes [0, 0, 6, 0, 55, 0, 85, 0]
       • For 243: digit = 4, place 243 at index 3.
         • count array becomes [2, 3, 3, 3, 3, 4, 5, 5, 6, 8].
         • output array becomes [0, 0, 6, 243, 55, 0, 85, 0]
       • For 903: digit = 0, place 903 at index 1.
         • count array becomes [1, 3, 3, 3, 3, 4, 5, 5, 6, 8].
         • output array becomes [0, 903, 6, 243, 55, 0, 85, 0]
       • For 2: digit = 0, place 2 at index 0.
         • count array becomes [0, 3, 3, 3, 3, 4, 5, 5, 6, 8].
         • output array becomes [2, 903, 6, 243, 55, 0, 85, 0]
       • For 90: digit = 9, place 90 at index 7.
         • count array becomes [0, 3, 3, 3, 3, 4, 5, 5, 6, 7].
         • output array becomes [2, 903, 6, 243, 55, 0, 85, 90]
       • For 180: digit = 8, place 180 at index 5.
         • count array becomes [0, 3, 3, 3, 3, 4, 5, 5, 5, 7].
         • output array becomes [2, 903, 6, 243, 55, 180, 85, 90]

   • Copy to Original Array:

     • array becomes [2, 903, 6, 243, 55, 180, 85, 90]

4. Digit Position: Hundreds (exp = 100)

   • Count Digit Occurrences:

     • Initialize count array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Counting digit occurrences:
       • count: [5, 1, 1, 0, 0, 0, 0, 0, 0, 1]

   • Cumulative Count:

     • Cumulative count array: [5, 6, 7, 7, 7, 7, 7, 7, 7, 8]

   • Build Output Array:

     • Traverse the input array in reverse order:
       • For 90: digit = 0, place 90 at index 4.
         • count array becomes [4, 6, 7, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 0, 0, 0, 90, 0, 0, 0]
       • For 85: digit = 0, place 85 at index 3.
         • count array becomes [3, 6, 7, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 0, 0, 85, 90, 0, 0, 0]
       • For 180: digit = 1, place 180 at index 5.
         • count array becomes [3, 5, 7, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 0, 0, 85, 90, 180, 0, 0]
       • For 55: digit = 0, place 55 at index 2.
         • count array becomes [2, 5, 7, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 0, 55, 85, 90, 180, 0, 0]
       • For 243: digit = 2, place 243 at index 6.
         • count array becomes [2, 5, 6, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 0, 55, 85, 90, 180, 243, 0]
       • For 6: digit = 0, place 6 at index 1.
         • count array becomes [1, 5, 6, 7, 7, 7, 7, 7, 7, 8].
         • output array becomes [0, 6, 55, 85, 90, 180, 243, 0]
       • For 903: digit = 9, place 903 at index 7.
         • count array becomes [1, 5, 6, 7, 7, 7, 7, 7, 7, 7].
         • output array becomes [0, 6, 55, 85, 90, 180, 243, 903]
       • For 2: digit = 0, place 2 at index 0.
         • count array becomes [0, 5, 6, 7, 7, 7, 7, 7, 7, 7].
         • output array becomes [2, 6, 55, 85, 90, 180, 243, 903]

   • Copy to Original Array:

     • array becomes [2, 6, 55, 85, 90, 180, 243, 903]

Code

Complexity Analysis

Time Complexity

• Finding the maximum value: O(n)
• Counting Sort for each digit:
  • Counting occurrences: O(n)
  • Building the cumulative count: O(k)
  • Placing numbers in the output array: O(n)
  • Copying back to the original array: O(n)
• Number of digits (d): log_b(k), where k is the range of input values and b is the base (10 for decimal system).

Overall time complexity: O(d * (n + k)), where d is the number of digits, n is the number of elements, and k is the range of the digits.

Space Complexity

• Count array: O(k)
• Output array: O(n)

Overall space complexity: $O(n + k)%

Real-Time Applications of Radix Sort

• Sorting large integers: Useful for sorting large sets of integers efficiently.
• Fixed-length string sorting: Sorting fixed-length strings, such as sorting by date or IP addresses.
• Telephone numbers: Sorting telephone numbers where the number of digits is fixed.
• Account numbers: Organizing bank account numbers which are typically of fixed length.
• Postcode sorting: Efficiently sorting postcodes or ZIP codes.
• Data processing in databases: Optimizing the sorting of fixed-length keys in databases.
• Digital image processing: Sorting pixel values in image processing applications where each pixel can be treated as a multi-digit number.