Radix Sort Algorithm

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

import java.util.Arrays;

public class Solution {

  // Function to get the maximum value in the array
  private static int getMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
      if (array[i] > max) {
        max = array[i];
      }
    }
    return max;
  }

  // Function to perform Counting Sort on the array based on the digit represented by exp
  private static void countingSort(int[] array, int exp) {
    int n = array.length;
    int[] output = new int[n]; // Output array to store sorted numbers
    int[] count = new int[10]; // Count array to store the count of digits (0-9)

    // Initialize count array with all zeros
    Arrays.fill(count, 0);

    // Store count of occurrences of each digit in count[]
    for (int i = 0; i < n; i++) {
      int digit = (array[i] / exp) % 10;
      count[digit]++;
    }

    // Update count array to contain the actual position of each digit in the output[]
    for (int i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    // Build the output array by placing the numbers in their correct positions
    // Traverse the input array in reverse order to maintain stable sorting
    for (int i = n - 1; i >= 0; i--) {
      int digit = (array[i] / exp) % 10;
      // Place the number in the output array at the index of its position
      output[count[digit] - 1] = array[i];
      // Decrement the count of the current digit
      count[digit]--;
    }

    // Copy the sorted numbers back into the original array
    for (int i = 0; i < n; i++) {
      array[i] = output[i];
    }
  }

  // Function to perform Radix Sort
  public void radixSort(int[] array) {
    // Find the maximum number to determine the number of digits
    int max = getMax(array);

    // Perform counting sort for every digit. Note that exp is 10^i where i is the current digit number
    for (int exp = 1; max / exp > 0; exp *= 10) {
      countingSort(array, exp);
    }
  }

  // Main method to test Radix Sort with 3 examples
  public static void main(String[] args) {
    // Example 1
    int[] array1 = { 180, 55, 85, 90, 903, 243, 2, 6 };
    Solution sol = new Solution();
    sol.radixSort(array1);
    System.out.println("Sorted array 1: " + Arrays.toString(array1));

    // Example 2
    int[] array2 = { 123, 456, 789, 234, 567, 890, 345, 678 };
    sol.radixSort(array2);
    System.out.println("Sorted array 2: " + Arrays.toString(array2));

    // Example 3
    int[] array3 = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    sol.radixSort(array3);
    System.out.println("Sorted array 3: " + Arrays.toString(array3));
  }
}

Complexity Analysis

Time Complexity

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

Overall time complexity: , 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:
• Output array:

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.

I just read a lesson on **Radix Sort Algorithm** (DSA) and want to truly understand it. Explain Radix Sort Algorithm from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Radix Sort Algorithm** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Radix Sort Algorithm** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Radix Sort Algorithm** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.