Radixsort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position. To sort these specific positions data counting sort as a subroutine.

Counting sort is a linear time sorting algorithm that sort in O(n+k) but that will worst in case of items range from 1 to n2 that sort in O(n^2). Where K is items range from 1 to k.

Note :

• LSD : Least Significant Digit
• MSD : Most Significant Digit

Steps to Radixsort

1. Check for the max length item in input values and check for length.
2. For each digit position i where i varies from LSD to the MSD.
3. Perform counting sort based on considering key as i position digits.
4. Finally, you will get a sorting array for input items.

Points to Remember

• Data Structure: Array
• Best Time Complexity: Ω(nk)
• Average Time Complexity: Θ(nk)
• Worst Time Complexity: O(nk)
• Worst Space Complexity: O(n+k)

Radix sort Example

Input Numbers:

        170, 45, 75, 90, 02, 802, 2, 66 
Step 1 : Find the max item length in input i.e 3.

Step 2: Repeat the below process for position i from LSD to MSD
        Perform count sort on numbers, after considering digits as key on 
        particular i.
        
        0 Position :
        170, 90, 02, 802, 2, 45, 75, 66
        
        1 Position :
        02, 2, 802, 45, 66, 170, 75, 90
        
        2 Position :
        02, 2, 45, 66, 75, 90, 170, 802 
        
Step 3: Final Redix Sort result

        02, 2, 45, 66, 75, 90, 170, 802    
 

Radix Sort Program

public class RadixSort {

public static void main(String[] args) {

// Assuming our key values are with in range 0 - 9
int[] items = { 170, 45, 75, 90, 02, 802, 2, 66 };
System.out.println("Before Radix Sorting :");
printArray(items);

// Perform counting sort sort
radixsort(items);

System.out.println("After Radix Sorting :");
printArray(items);
}

// radix sort method to sort values of array items
static void radixsort(int items[]) {
// find max number to know max number of digits
int m = getMax(items);

// Perform counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countingsort(items, exp);
}

// A utility method to get maximum value in items[]
static int getMax(int items[]) {
int max = items[0];
for (int i = 1; i  max)
max = items[i];
return max;
}

private static void countingsort(int[] items, int exp) {
// create array of size 10 that will have index value as 0-9
// it will create array of size 10 and initialize
// each element with value 0
int[] counts = new int[10];
int[] output = new int[items.length];
for (int key : items) {
// for each match key, index position element
// increase count as 1
counts[(key / exp) % 10] += 1;
}

// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (int i = 1; i = 0; i--) {
output[counts[(items[i] / exp) % 10] - 1] = items[i];
counts[(items[i] / exp) % 10] -= 1;
}

// Copy the output array to items[] to return
// sorted array according to index position
for (int i = 0; i < items.length; i++)
items[i] = output[i];

}

static void printArray(int items[]) {
for (int item : items) {
System.out.print(item + " ");
}
System.out.println();
}

}

Output

Before Radix Sorting :
170 45 75 90 2 802 2 66 
After Radix Sorting :
2 2 45 66 75 90 170 802