×

Courses

Chapters

>
<

Data Structure

Radix Sort | CrackEase

Radix Sort

What is Radix sort?

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by processing individual digits. It is commonly used when keys are integers or strings with a fixed length. Instead of comparing elements directly, Radix sort distributes elements into buckets according to each digit (or character) and processes them digit by digit.

Example idea: to alphabetize names you can first group by the first letter (A–Z), then within each group sort by the second letter, and so on. Radix sort follows a similar multi-pass approach for numeric digits (ones, tens, hundreds...).

Typical time complexity: O(d·(n + k)), where d is number of digits, n is number of elements, and k is range of each digit (e.g., 10 for decimal). Space complexity is O(n + k). For some inputs (small d or limited key range) Radix sort can outperform comparison sorts like quicksort.

Implementation of Radix sort

Let us take an example to understand Radix sort.

Given the list: (248, 140, 261, 323, 438, 120, 221, 443, 266).

Phase A (ones digit): Sort numbers into buckets by their ones digit, collect buckets from 0 to 9 and reassemble.

Implementation of Radix sort

Phase B (tens digit): Sort by the tens digit using the current order (stable), collect buckets and reassemble.

Radix sort process diagram
Implementation of Radix sort

Phase C (hundreds digit): Sort by the hundreds digit (if present) and collect. After these passes the list becomes fully sorted.

Result

Final sorted list (ascending): (120, 140, 221, 248, 261, 266, 323, 438, 443).

Code
  
// Radix Sort in C Programming

#include <stdio.h>
#include <stdlib.h>

/* A stable counting sort used by radixsort.
   This sorts array[] according to the digit represented by place (1, 10, 100, ...) */
void countingSort(int array[], int size, int place) {
    int output[size]; // output array
    int count[10] = {0};

    // Count occurrences of digits (0..9)
    for (int i = 0; i < size; i++) {
        int digit = (array[i] / place) % 10;
        count[digit]++;
    }

    // Convert count to cumulative count (positions)
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array (iterate from end to make it stable)
    for (int i = size - 1; i >= 0; i--) {
        int digit = (array[i] / place) % 10;
        output[count[digit] - 1] = array[i];
        count[digit]--;
    }

    // Copy the output array to array[], so that array[] now contains sorted numbers by current digit
    for (int i = 0; i < size; i++)
        array[i] = output[i];
}

// Utility function to get maximum value in array
int getMax(int array[], int n) {
    int max = array[0];
    for (int i = 1; i < n; i++)
        if (array[i] > max)
            max = array[i];
    return max;
}

// Main radix sort that sorts array[] of size n
void radixsort(int array[], int size) {
    // Find the maximum number to know number of digits
    int max = getMax(array, size);

    // Do counting sort for every digit. Note that instead
    // of passing digit number, place is passed. place is 10^i
    // where i is current digit number
    for (int place = 1; max / place > 0; place *= 10)
        countingSort(array, size, place);
}

// Print an array
void printArray(int array[], int size) {
    for (int i = 0; i < size; ++i)
        printf("%d ", array[i]);
    printf("\n");
}

// Driver code
int main() {
    int array[] = {121, 432, 564, 23, 1, 45, 788};
    int n = sizeof(array) / sizeof(array[0]);

    radixsort(array, n);

    printf("Sorted Array in Ascending Order: \n");
    printArray(array, n);

    return 0;
}
  

  
#include <iostream>
#include <vector>
using namespace std;

// A stable counting sort used by radixSort for digit represented by 'place'
void countingSort(int array[], int size, int place) {
    const int RADIX = 10;
    vector output(size);
    int count[RADIX] = {0};

    // Count occurrences of digits (0..9)
    for (int i = 0; i < size; i++) {
        int digit = (array[i] / place) % 10;
        count[digit]++;
    }

    // Cumulative count
    for (int i = 1; i < RADIX; i++) count[i] += count[i - 1];

    // Build the output array (stable) — iterate from end
    for (int i = size - 1; i >= 0; i--) {
        int digit = (array[i] / place) % 10;
        output[count[digit] - 1] = array[i];
        count[digit]--;
    }

    // Copy back to original array
    for (int i = 0; i < size; i++) array[i] = output[i];
}

// Utility to get max element
int getMax(int array[], int n) {
    int mx = array[0];
    for (int i = 1; i < n; i++)
        if (array[i] > mx) mx = array[i];
    return mx;
}

void radixsort(int array[], int size) {
    int mx = getMax(array, size);
    for (int place = 1; mx / place > 0; place *= 10)
        countingSort(array, size, place);
}

void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int array[] = {121, 432, 564, 23, 1, 45, 788};
    int n = sizeof(array) / sizeof(array[0]);

    radixsort(array, n);

    cout << "Sorted Array in Ascending Order:" << endl;
    printArray(array, n);
    return 0;
}
  

  
class RadixSort {

  // A stable counting sort used by radixSort
  void countingSort(int[] array, int size, int place) {
    int[] output = new int[size];
    int[] count = new int[10];

    // Count occurrences of digits (0..9)
    for (int i = 0; i < size; i++) {
      int digit = (array[i] / place) % 10;
      count[digit]++;
    }

    // Cumulative count
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];

    // Build the output array (stable) — iterate from end
    for (int i = size - 1; i >= 0; i--) {
      int digit = (array[i] / place) % 10;
      output[count[digit] - 1] = array[i];
      count[digit]--;
    }

    // Copy back to original array
    for (int i = 0; i < size; i++) array[i] = output[i];
  }

  // Utility to get max element
  int getMax(int[] array, int n) {
    int mx = array[0];
    for (int i = 1; i < n; i++)
      if (array[i] > mx) mx = array[i];
    return mx;
  }

  // Main radix sort
  void radixSort(int[] array, int size) {
    int mx = getMax(array, size);
    for (int place = 1; mx / place > 0; place *= 10)
      countingSort(array, size, place);
  }

  // Print an array
  static void printArray(int[] array, int size) {
    for (int i = 0; i < size; i++)
      System.out.print(array[i] + " ");
    System.out.println();
  }

  public static void main(String[] args) {
    int[] data = {121, 432, 564, 23, 1, 45, 788};
    RadixSort rs = new RadixSort();
    rs.radixSort(data, data.length);
    System.out.println("Sorted Array in Ascending Order: ");
    printArray(data, data.length);
  }
}
	

	
Sorted Array in Ascending Order: 
1 23 45 121 432 564 788
Time Complexity for Radix Sort
BestAverageWorstSpace ComplexityNotes
O(d·(n + k))O(d·(n + k))O(d·(n + k))O(n + k)Here d is digits, k is digit range (10 for decimal).
Footer Content | CrackEase
→
←