Radix sort is a generalization of a bucket sort. Radix sort is a linear sorting algorithm that is used to sort integers.

Radix sort performs digit sorting from the least significant to the most significant digit.

To sort decimal numbers, where the radix or base is 10, we need 10 buckets. These buckets are numbered from 0 – 9.

A radix sort works similarly to sorting students’ names alphabetically.

For the first pass, numbers are sorted by the least significant digit. Numbers with same least significant digit are stored in the same bucket.

In the second pass, numbers are sorted by the second least significant digit.

The numbers in buckets are merged at the end of every pass to produce a common list.

Number of passes depends on the range of numbers being sorted.

Time Complexity

Best Case Ω (n + k): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case θ (n k): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O (n k): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

The space complexity of radix sorting is O (n + k).

Example

C Program

#include <stdio.h>  
  
int getMax(int a[], int n) {  
    int max = a[0];  
    for(int i = 1; i<n; i++) {  
        if(a[i] > max)  
            max = a[i];  
    }  
    //maximum element from the array  
    return max; 
}  

// function to implement counting sort  
void countingSort(int a[], int n, int place) {  
    int output[n + 1];  
    int count[10] = {0};    
  
    // Calculate count of elements  
    for (int i = 0; i < n; i++)  
        count[(a[i] / place) % 10]++;  
      
    // Calculate cumulative frequency  
    for (int i = 1; i < 10; i++)  
        count[i] += count[i - 1];  
  
    // Place the elements in sorted order  
    for (int i = n - 1; i >= 0; i--) {  
        output[count[(a[i] / place) % 10] - 1] = a[i];  
        count[(a[i] / place) % 10]--;  
    }  
  
    for (int i = 0; i < n; i++)  
        a[i] = output[i];  
}  
  
// function to implement radix sort  
void radix_sort(int a[], int n) {  
    // get maximum element from array  
    int max = getMax(a, n);  
  
    // Apply counting sort to sort elements based on place value  
    for (int place = 1; max / place > 0; place *= 10)  
        countingSort(a, n, place);  
}  
  
// function to print array elements  
void print(int a[], int n) {  
    for (int i = 0; i < n; ++i)       
        printf("%d  ", a[i]);  
   
    printf("n");  
}  
  
int main() {  
  int a[] = {11, 289, 380, 222, 145, 920, 514, 777, 122};  
  int n = sizeof(a) / sizeof(a[0]);  
  printf("Before sorting array elements are - n");  
  print(a,n);  
  radix_sort(a, n);  
  printf("After applying Radix sort, the array elements are - n");  
  print(a, n);  
}  

Java Program

class RadixSort { 
    
    static int getMax(int a[], int n) {  
        int max = a[0];  
        for(int i = 1; i<n; i++) {  
            if(a[i] > max)  
                max = a[i];  
        }  
        //maximum element from the array  
        return max; 
    }  
      
    // function to implement counting sort 
    static void countingSort(int a[], int n, int place) {  
        int[] output = new int[n+1];  
        int[] count = new int[10];  
      
        // Calculate count of elements  
        for (int i = 0; i < n; i++)  
            count[(a[i] / place) % 10]++;  
          
        // Calculate cumulative frequency  
        for (int i = 1; i < 10; i++)  
            count[i] += count[i - 1];  
      
        // Place the elements in sorted order  
        for (int i = n - 1; i >= 0; i--) {  
            output[count[(a[i] / place) % 10] - 1] = a[i];  
            count[(a[i] / place) % 10]--;  
        }  
      
        for (int i = 0; i < n; i++)  
            a[i] = output[i];  
    }  
      
    // function to implement radix sort  
    static void radixSort(int a[], int n) {  
        // get maximum element from array  
        int max = getMax(a, n);  
      
        // Apply counting sort to sort elements based on place value
        for (int place = 1; max / place > 0; place *= 10)  
            countingSort(a, n, place);  
    }  
      
    // function to print array elements  
    static void print(int a[], int n) {  
        for (int i = 0; i < n; ++i)   
            System.out.print(a[i] + " ");  
    }  
      
      public static void main(String args[]) {  
          int a[] = {11, 289, 380, 222, 145, 920, 514, 777, 122};    
          int n = a.length;  
          System.out.print("Before sorting array elements are - n");  
          print(a, n);  
          
          radixSort(a, n);  
          System.out.print("nnAfter applying Radix sort, the array elements are -  n");  
          print(a, n);  
    }  
}