Radix Sort is a noncomparative, integer sorting algorithm that sorts numbers by processing individual digits. Unlike other sorting algorithms, such as Quick Sort or Merge Sort, Radix Sort works by sorting numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It leverages Counting Sort as a subroutine to sort numbers based on individual digits.
Approach
Radix Sort works by sorting the numbers in the array based on each digit, starting from the least significant digit (units place) to the most significant digit. The core of the approach involves the following steps:

Finding the Maximum Number:
 First, determine the maximum number in the array. The number of digits in this maximum number will determine the number of passes (iterations) the algorithm needs to perform.

Sorting by Each Digit:
 For each digit place (units, tens, hundreds, etc.), the algorithm uses Counting Sort to sort the array based on that specific digit. Counting Sort is chosen because it is a stable, lineartime sorting algorithm that works efficiently when sorting digits.
 The sorting is performed starting from the least significant digit and moving towards the most significant digit. This ensures that the array remains sorted with respect to the lowerorder digits when sorting by higherorder digits.

Iterating for Each Digit:
 The process of digitwise sorting is repeated until all digits have been processed. For example, if the maximum number in the array has three digits, the array will be sorted three timesâ€”once for each digit.
Code Explanation
// Function to get the maximum value in the array
int getMax(vector<int>& arr) {
return *max_element(arr.begin(), arr.end());
}
// Counting Sort function to sort based on a specific digit (exp)
void countingSort(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n);
int count[10] = {0}; // Since we're dealing with digits (09), we use a fixed array of size 10
// Count the occurrences of each digit in the given place (exp)
for (int i = 0; i < n; ++i) {
count[(arr[i] / exp) % 10]++;
}
// Compute cumulative count to determine positions
for (int i = 1; i < 10; ++i) {
count[i] += count[i  1];
}
// Build the output array using the count array
for (int i = n  1; i >= 0; i) {
output[count[(arr[i] / exp) % 10]  1] = arr[i];
count[(arr[i] / exp) % 10];
}
// Copy the sorted array back to the original array
for (int i = 0; i < n; ++i) {
arr[i] = output[i];
}
}
// Radix Sort function
void radixSort(vector<int>& arr) {
// Find the maximum number to determine the number of digits
int max_val = getMax(arr);
// Perform counting sort for every digit. exp is 10^i (i.e., 1, 10, 100, ...)
for (int exp = 1; max_val / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
How It Works

DigitbyDigit Sorting:
 The
countingSort
function is applied to each digit place (exp
). For example, whenexp = 1
, the function sorts the array by the units place; whenexp = 10
, it sorts by the tens place, and so on.
 The

Stability:
 Counting Sort, used within Radix Sort, is a stable sorting algorithm. This means that numbers with the same digit in the current place retain their relative order from the previous digitâ€™s sort. This stability is crucial for Radix Sort to function correctly.

Iteration:
 The loop in the
radixSort
function continues until all digits of the maximum number have been processed. This ensures that the array is fully sorted by the time the loop completes.
 The loop in the
Complexity Analysis

Time Complexity:
 The time complexity of Radix Sort is O(nk), where
n
is the number of elements in the array, andk
is the number of digits in the maximum number. Sincek
is typically much smaller thann
, Radix Sort is often considered to have linear time complexity, making it efficient for large datasets.
 The time complexity of Radix Sort is O(nk), where

Space Complexity:
 The space complexity of Radix Sort is O(n + k), where
n
is for the output array used in Counting Sort, andk
is the fixed size of the counting array (which is 10 in the case of base10 numbers).
 The space complexity of Radix Sort is O(n + k), where