Radix Sort Program with Explanation and Code

2025-11-19 radix sort non-comparative sorting counting sort based sorting digit sorting LSD radix sort algorithm programs sorting algorithms python radix sort c radix sort javascript radix sort php radix sort csharp radix sort data structures

Radix Sort is a fast, non-comparative sorting algorithm that sorts numbers digit-by-digit using Counting Sort. This page explains Radix Sort with simple steps and provides full implementations in Python, C, JavaScript, PHP, and C#. Perfect for students and algorithm practice.

Program Explanation

What is Radix Sort?

Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It uses a stable intermediate sorting algorithm like Counting Sort to sort individual digits. Radix Sort is efficient for sorting large numbers when the number of digits is small.

Steps to Solve

  1. Find the number with the maximum digits in the array.
  2. Set the digit position (exp = 1, 10, 100, …).
  3. Use Counting Sort to sort elements based on the current digit.
  4. Repeat the process for every digit position.
  5. Stop when the largest digit position has been sorted.
  6. Final array becomes fully sorted after all digit passes.

Key Points

  • Does not use comparison between elements.
  • Time complexity: O(d × (n + k)).
  • Works best for integers with fixed digit length.
  • Stable sorting when Counting Sort is stable.
  • Used for sorting IDs, phone numbers, and large integer datasets.

Program Code


def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        index = (num // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

arr = list(map(int, input("Enter numbers: ").split()))
radix_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.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, int exp) {
    int output[n];
    int count[10] = {0};

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

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

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

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int max = getMax(arr, n);
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

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

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

    radixSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function countingSort(arr, exp) {
  let output = Array(arr.length).fill(0);
  let count = Array(10).fill(0);

  for (let num of arr)
    count[Math.floor(num / exp) % 10]++;

  for (let i = 1; i < 10; i++)
    count[i] += count[i - 1];

  for (let i = arr.length - 1; i >= 0; i--) {
    let index = Math.floor(arr[i] / exp) % 10;
    output[count[index] - 1] = arr[i];
    count[index]--;
  }

  for (let i = 0; i < arr.length; i++)
    arr[i] = output[i];
}

function radixSort(arr) {
  let max = Math.max(...arr);
  let exp = 1;

  while (Math.floor(max / exp) > 0) {
    countingSort(arr, exp);
    exp *= 10;
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
radixSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static int GetMax(int[] arr) {
        int max = arr[0];
        foreach (int num in arr)
            if (num > max) max = num;
        return max;
    }

    static void CountingSort(int[] arr, int exp) {
        int n = arr.Length;
        int[] output = new int[n];
        int[] count = new int[10];

        foreach (int num in arr)
            count[(num / exp) % 10]++;

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

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

        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }

    static void RadixSort(int[] arr) {
        int max = GetMax(arr);
        for (int exp = 1; max / exp > 0; exp *= 10)
            CountingSort(arr, exp);
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        RadixSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function countingSort(&$arr, $exp) {
    $n = count($arr);
    $output = array_fill(0, $n, 0);
    $count = array_fill(0, 10, 0);

    foreach ($arr as $num)
        $count[intval($num / $exp) % 10]++;

    for ($i = 1; $i < 10; $i++)
        $count[$i] += $count[$i - 1];

    for ($i = $n - 1; $i >= 0; $i--) {
        $index = intval($arr[$i] / $exp) % 10;
        $output[$count[$index] - 1] = $arr[$i];
        $count[$index]--;
    }

    for ($i = 0; $i < $n; $i++)
        $arr[$i] = $output[$i];
}

function radixSort(&$arr) {
    $max = max($arr);
    for ($exp = 1; intval($max / $exp) > 0; $exp *= 10)
        countingSort($arr, $exp);
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
radixSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1