1. Introduction

Radix Sort is a non-comparative sorting algorithm that processes the integer representations of the numbers to be sorted digit by digit, starting from the least significant digit (LSD) and proceeding to the most significant digit (MSD) or vice-versa. The idea is to use counting sort (or any other stable sort) as a subroutine to sort numbers based on individual digits.

2. Program Steps

1. Find the maximum number in the list to know the number of digits.

2. Start from the least significant digit and use counting sort as a subroutine to sort the list.

3. Repeat the process for each significant digit.

3. Code Program

public class RadixSort {

    // A utility function to get the maximum value in arr[]
    static int getMax(int arr[], int n) {
        int mx = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > mx)
                mx = arr[i];
        return mx;
    }

    // A function to do counting sort based on the digit represented by exp
    static void countSort(int arr[], int n, int exp) {
        int output[] = new int[n];
        int count[] = new int[10];
        int i;

        // Initialize count array
        for (i = 0; i < 10; i++)
            count[i] = 0;

        // Store count of occurrences
        for (i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;

        // Change count[i] so that count[i] now contains actual position of this digit in output[]
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the output array
        for (i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // Copy the output array to arr[] so that arr[] contains sorted numbers according to current digit
        for (i = 0; i < n; i++)
            arr[i] = output[i];
    }

    // Main radixSort function
    static void radixSort(int arr[], int n) {
        int m = getMax(arr, n);

        // Do counting sort for every digit
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

    // Driver Code
    public static void main(String[] args) {
        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
        int n = arr.length;

        radixSort(arr, n);

        System.out.println("Sorted array:");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

Output:

Sorted array:
2 24 45 66 75 90 170 802

4. Step By Step Explanation

1. getMax function: This utility function retrieves the maximum value from the array to determine the number of digits in the maximum number.

2. countSort function: This subroutine sorts the numbers based on individual digits using a counting sort mechanism. For each digit, it builds a frequency array, and then computes a prefix sum of the frequency to determine positions in the output array.

3. radixSort function: This is the main function that applies the countSort function on every digit starting from the least significant. The maximum number of digits is determined by the maximum number in the array.

4. Radix Sort leverages the fact that the number of digits in the numbers to be sorted is not very large, making it useful for sorting large lists/arrays of numbers.

Remember, Radix Sort is a linear time sorting algorithm when the number of digits is constant. It's not a comparison-based sort, and its performance is dependent on the number of digits in the numbers to be sorted.