Home » C Program » Radix Sort: Algorithm, Program, Explanation and Examples

Radix Sort: Algorithm, Program, Explanation and Examples

Last updated:

Support this post with a reaction:

3,263 views

What Is Radix Sort Algorithm?

Radix Sort is a non-comparison-based sorting algorithm that sorts elements by processing individual digits or characters instead of comparing entire values.

It works by sorting numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD), or vice versa.

Radix Sort commonly uses a stable sorting algorithm such as Counting Sort to arrange elements at each digit position.

For example, consider the following array:

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

Radix Sort processes the numbers based on:

  1. Units place (ones digit).
  2. Tens place.
  3. Hundreds place.

After processing all required digit positions, the array becomes:

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

Key point: Radix Sort does not compare complete numbers. It sorts them using individual digits and a stable sorting technique.

Characteristics of Radix Sort

The important characteristics of Radix Sort are:

  • It is a non-comparison-based sorting algorithm.
  • It sorts elements digit by digit.
  • It commonly uses Counting Sort as an intermediate sorting algorithm.
  • It can achieve linear-time performance when the number of digit positions and the base are suitably bounded.
  • It is a stable sorting algorithm when its intermediate sorting method is stable.
  • It requires additional memory for intermediate sorting.
  • It is useful for sorting integers, fixed-length strings, and structured numeric keys.

Types of Radix Sort

Radix Sort is mainly classified into two types based on the direction in which digits are processed.

1. Least Significant Digit (LSD) Radix Sort

LSD Radix Sort starts sorting from the rightmost digit (units place) and gradually moves towards the leftmost digit (most significant place).

2. Most Significant Digit (MSD) Radix Sort

MSD Radix Sort starts sorting from the leftmost digit (most significant place) and gradually processes the remaining digits.

1. Least Significant Digit (LSD) Radix Sort

LSD Radix Sort begins with the last digit of each number and processes the remaining digits from right to left.

Example of LSD:

Original Array:
170, 45, 75, 90, 802, 24, 2, 66

Pass 1: Sort by units digit
Pass 2: Sort by tens digit
Pass 3: Sort by hundreds digit

Final Sorted Array:
2, 24, 45, 66, 75, 90, 170, 802

LSD Radix Sort is commonly implemented using stable Counting Sort for each digit position.

2. Most Significant Digit (MSD) Radix Sort

MSD Radix Sort starts processing from the leftmost digit of each number.

It groups elements according to their most significant digit and then recursively sorts the individual groups using the remaining digits.

Example of MSD:

Consider:

329, 457, 657, 839, 436, 720, 355

First, group the numbers based on their hundreds digit:

Hundreds digitNumbers
3329, 355
4457, 436
6657
7720
8839

Next, sort each group using the remaining digits.

Final sorted array:

329, 355, 436, 457, 657, 720, 839

MSD Radix Sort is particularly useful in string sorting and applications where keys can be divided into groups based on their leading characters.

Radix sort working

Let’s understand the working of LSD Radix Sort using a simple example.

Consider the following array:

[170, 45, 75, 90, 802, 24, 2, 66]

We use Counting Sort to sort the elements according to each digit position.

Step 1: Find the Maximum Element

First, identify the largest number in the array.

Maximum element = 802

The maximum number contains three digits.

Therefore, we need three passes:

  • First pass: Units place.
  • Second pass: Tens place.
  • Third pass: Hundreds place.

Step 2: Sort According to the Units Digit

Extract the units digit using:

Digit=⌊Number1⌋mod10 \text{Digit}=\left\lfloor\frac{Number}{1}\right\rfloor \bmod 10
NumberUnits digit
1700
455
755
900
8022
244
22
666

After stable sorting based on the units digit:

[170, 90, 802, 2, 24, 45, 75, 66]

Step 3: Sort According to the Tens Digit

Now extract the tens digit using:

Digit=⌊Number10⌋mod10 \text{Digit}=\left\lfloor\frac{Number}{10}\right\rfloor \bmod 10
NumberTens digit
1707
909
8020
20
242
454
757
666

After stable sorting based on the tens digit:

[802, 2, 24, 45, 66, 170, 75, 90]

Step 4: Sort According to the Hundreds Digit

Now extract the hundreds digit using:

Digit=⌊Number100⌋mod10\text{Digit}=\left\lfloor\frac{Number}{100}\right\rfloor \bmod 10
NumberHundreds digit
8028
20
240
450
660
1701
750
900

After stable sorting based on the hundreds digit:

[2, 24, 45, 66, 75, 90, 170, 802]

Final sorted array

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

Radix Sort Algorithm

Input: An array ARR containing non-negative integers.

Output: The array sorted in ascending order.

  1. Start.
  2. Find the maximum element in the array.
  3. Initialize the digit position exp = 1.
  4. Repeat while max / exp > 0:
    • Apply Counting Sort based on the current digit.
    • Update the digit position by multiplying exp by 10.
  5. Repeat until all digit positions are processed.
  6. Display the sorted array.
  7. Stop.

Radix Sort Algorithm (Pseudocode)

RADIX_SORT(ARR, n)

1. Find MAX element in ARR
2. Set EXP = 1

3. WHILE MAX / EXP > 0

      COUNTING_SORT(ARR, n, EXP)

      EXP = EXP * 10

   END WHILE

4. RETURN ARR

Counting Sort Pseudocode Used in Radix Sort

COUNTING_SORT(ARR, n, EXP)

1. Create OUTPUT array of size n
2. Initialize COUNT array of size 10 with zeros

3. FOR i = 0 to n-1
      DIGIT = (ARR[i] / EXP) % 10
      COUNT[DIGIT]++

4. FOR i = 1 to 9
      COUNT[i] = COUNT[i] + COUNT[i-1]

5. FOR i = n-1 down to 0
      DIGIT = (ARR[i] / EXP) % 10
      OUTPUT[COUNT[DIGIT] - 1] = ARR[i]
      COUNT[DIGIT]--

6. FOR i = 0 to n-1
      ARR[i] = OUTPUT[i]

7. RETURN ARR

Radix Sort Program in C

The following C program implements LSD Radix Sort using Counting Sort. It accepts non-negative integers and sorts them in ascending order.

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

int getMax(int arr[], int n) {
    int max = arr[0];

    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    return max;
}

void countingSort(int arr[], int n, long long exp) {

    int *output = malloc(n * sizeof(int));
    int count[10] = {0};

    if (output == NULL) {
        printf("Memory allocation failed.");
        exit(1);
    }

    // Count digit occurrences
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // Calculate cumulative count
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build output array from right to left
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;

        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // Copy sorted elements back
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(output);
}

void radixSort(int arr[], int n) {

    int max = getMax(arr, n);

    for (long long exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {

    int n;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    if (n <= 0) {
        printf("Invalid array size.");
        return 0;
    }

    int *arr = malloc(n * sizeof(int));

    if (arr == NULL) {
        printf("Memory allocation failed.");
        return 1;
    }

    printf("Enter array elements:\n");

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);

        if (arr[i] < 0) {
            printf("Radix Sort implementation accepts only non-negative integers.");
            free(arr);
            return 1;
        }
    }

    printf("Before sorting:\n");

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    radixSort(arr, n);

    printf("\nAfter sorting:\n");

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    free(arr);

    return 0;
}

Output

Enter the number of elements: 5

Enter array elements:
23 11 43 56 12

Before sorting:
23 11 43 56 12

After sorting:
11 12 23 43 56

Radix Sort Complexity

ScenarioComplexityExplanation
Best CaseO(d × (n + b))Each digit is processed using stable Counting Sort.
Average CaseO(d × (n + b))Every digit position requires one complete sorting pass.
Worst CaseO(d × (n + b))The number of passes depends on the maximum number of digits, not the initial arrangement.
Space ComplexityO(n + b)Extra space is required for the output array and counting array.
Stable SortYesMaintains the relative order of elements having equal keys, provided the intermediate sorting algorithm is stable.
In-Place SortNoStandard Radix Sort implementations require additional memory.
Comparison-BasedNoSorts elements based on individual digits rather than comparing complete elements.