Radix Sort

Introduction

Radix Sort , Today we are going to explore one of the most fundamental yet fascinating topics in programming: radix sort.
sorting is a key part of almost every application — whether you’re arranging data for a report, processing transactions, or analyzing information. among all sorting techniques, radix sort stands out because of its unique, non-comparative approach. instead of comparing elements directly like quicksort or mergesort, radix sort distributes data based on the digits of the numbers, making it especially efficient for large datasets with fixed-length keys.

List of Content :

• Introduction to radix sort?
• Core concept and working principle
• Steps of radix sort algorithm
• Example walkthrough
• Implementation code in C++ , Java and C
• Time and space complexity
• Advantages and Disadvantages
• Comparison with other sorting algorithms

📖 Introduction to radix sort

Radix sort is a non-comparative sorting algorithm that organizes data by processing individual digits of the numbers rather than comparing the numbers directly. it takes advantage of the structure of the input — like the number of digits — to efficiently sort large lists of integers or strings of fixed length.

the core idea is to sort numbers digit-by-digit, starting either from the least significant digit (lsd) or the most significant digit (msd), and group them into intermediate “buckets.” by repeating this process for every digit, the algorithm gradually arranges the list into its fully sorted order.

⚙️ Core concept and working of radix sort

Radix sort works by sorting numbers one digit at a time. instead of comparing entire numbers, it looks at each digit position separately.

🧠 How it works:

• start from the least significant digit (the last digit).

• use a stable sort (like counting sort) to group numbers by that digit.

• move to the next digit to the left and repeat the process.

• continue until all digits are processed.

  by the end, the list is fully sorted. this method is very fast when you have lots of numbers with a fixed number of digits because it doesn’t do any direct comparisons — it just organizes by digits. ✅

📝 Steps of the radix sort algorithm

1. Find the largest number in the list to know the total number of digits.

2. Set digit position = least significant digit (lsd) (the rightmost digit).

3. Use a stable sort (often counting sort) to sort the numbers based on this digit.

4. Move to the next digit to the left.

5. Repeat sorting by the current digit position until all digits have been processed.

6. Once all digits are sorted, the list is fully sorted.

✅ That’s the basic step-by-step process of radix sort!

🔍 Example walkthrough of radix sort

let’s sort the list:

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

1️⃣ Sort by the least significant digit (units place):
look at the last digit of each number and group them:

170 → 0     90 → 0     802 → 2     2 → 2
24 → 4      45 → 5     75 → 5      66 → 6

after sorting by last digit:

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

2️⃣ Sort by the next digit (tens place):
look at the tens digit:

170 → 7     90 → 9     802 → 0     2 → 0
24 → 2      45 → 4     75 → 7      66 → 6

after sorting by tens digit:

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

3️⃣ Sort by the most significant digit (hundreds place):
look at the hundreds digit:

802 → 8     2 → 0     24 → 0     45 → 0
66 → 0      170 → 1    75 → 0     90 → 0

after sorting by hundreds digit:

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

✅ Final sorted list:

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

💻 Implementation of radix sort in C++, Java, and C

🔵 C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int getMax(vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

void countSort(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    int count[10] = {0};

    for (int num : arr) count[(num / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];

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

int main() {
    vector<int> arr = {170,45,75,90,802,24,2,66};
    int maxNum = getMax(arr);

    for (int exp = 1; maxNum/exp > 0; exp *= 10)
        countSort(arr, exp);

    for (int num : arr) cout << num << " ";
    return 0;
}

🔵 Java Implementation

import java.util.*;

class RadixSort {
    static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) if (num > max) max = num;
        return max;
    }

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

        for (int num : 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 num = arr[i];
            output[count[(num/exp)%10]-1] = num;
            count[(num/exp)%10]--;
        }

        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170,45,75,90,802,24,2,66};
        int max = getMax(arr);

        for (int exp = 1; max/exp > 0; exp *= 10)
            countSort(arr, exp);

        System.out.println(Arrays.toString(arr));
    }
}

🔵 C Implementation

#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 countSort(int arr[], int n, int exp) {
    int output[n], 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--) {
        output[count[(arr[i]/exp)%10]-1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {170,45,75,90,802,24,2,66};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max = getMax(arr, n);

    for (int exp = 1; max/exp > 0; exp *= 10)
        countSort(arr, n, exp);

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

⏱️ Time and Space complexity of radix sort

• Time complexity: O(n * k)
• Space complexity: O(n)

✅ Advantages of Radix Sort

• 🕒 Fast for large datasets when the number of digits (k) is small.
• ⚡ Linear time complexity in terms of n and k — often faster than comparison sorts like quicksort or mergesort.
• 🧠 Stable sort — preserves the relative order of equal elements.
• 🔧 No direct comparisons between elements; sorts by digits.
• 📏 Works efficiently with fixed-length integers or strings.

❌ Disadvantages of Radix Sort

• 🧮 Requires extra space for auxiliary arrays, so space complexity is O(n).
• 📊 Efficiency depends on the number of digits k — if k is large, performance degrades.
• ⚠️ Only suitable for data with a fixed number of digits (e.g. integers or strings of the same length).
• 🔄 Implementation is more complex than simple sorts like insertion sort or bubble sort.
• 🧩 Requires a stable sorting algorithm as a subroutine (e.g. counting sort), making it less self-contained.

🔍 Comparison with Other Sorting Algorithms

💡 Key Points:

• Radix Sort shines when sorting large lists of integers with a small number of digits.
• Unlike comparison sorts (quick, merge, heap), radix sort's time is independent of the order of elements.
• Its stable and non-comparative nature makes it ideal for specific datasets where traditional sorts might be slower.
  .
  .
  .

_for more topics Click Here.

Happy Coding!!