# Radix Sort

- Radix Sort Algorithm
- Radix Sort Example
- Radix Sort Algorithm Implementation
- Radix Sort Algorithm Complexity

If you don’t know what is counting sort, then please go through the counting sort article first.

Radix sort is a non-comparative sorting algorithm. This algorithm avoids comparisons by inserting elements into buckets according to the `radix`

(Radix/Base is the number of unique digits used to represent numbers. For example, decimal numbers have ten unique digits). It sorts elements based on the digits of individual elements. It performs counting sort on digits from least significant digit to the most significant digit. It has also been called bucket sort or digital sort and is very useful on parallel machines.

## Radix Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements.

##### Find the largest element

`maxm`

in the array.##### Sort each digit in

`maxm`

starting from least significant using a stable sorting algorithm.

## Radix Sort Example

Suppose we have the array: `(1851, 913, 1214, 312, 111, 23, 41, 9)`

. We will sort it using the radix sort algorithm.

Index | Input Array | First Iteration | Second Iteration | Third Iteration | Fourth Iteration |
---|---|---|---|---|---|

0 | 1851 | 1851 | 0009 | 0009 | 0009 |

1 | 0913 | 0111 | 0111 | 0023 | 0023 |

2 | 1214 | 0041 | 0312 | 0041 | 0041 |

3 | 0312 | 0312 | 0913 | 0111 | 0111 |

4 | 0111 | 0913 | 1214 | 1214 | 0312 |

5 | 0023 | 0023 | 0023 | 0312 | 0913 |

6 | 0041 | 1214 | 0041 | 1851 | 1214 |

7 | 0009 | 0009 | 1851 | 0913 | 1851 |

In the first iteration, we sort according to unit place and then moves towards tens, hundreds, and thousands place to get the final sorted array as `9, 23, 41, 111, 312, 913, 1214, 1851`

## Radix Sort Algorithm Implementation

```
#include<iostream>
using namespace std;
const int N = 10;
int maxm(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 place) {
int output[n];
int count[N];
for (int i = 0; i < N; ++i)
count[i] = 0;
for (int i = 0; i < n; i++)
count[(arr[i] / place) % 10]++;
for (int i = 1; i < N; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / place) % 10] - 1] = arr[i];
count[(arr[i] / place) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixsort(int arr[], int n) {
int max = maxm(arr, n);
for (int place = 1; max / place > 0; place *= 10)
countingSort(arr, n, place);
}
int main() {
int n = 5;
int arr[5] = {1851, 913, 1214, 312, 111};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
radixsort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Radix Sort Algorithm Complexity

### Time Complexity

- Average Case

Radix sort has a time complexity of `O(n + b)`

where `b`

is the range of input. If there are `d`

digits in the maximum element `maxm`

, then the time complexity of Radix Sort becomes `O(d*(n + b))`

. Since d and b are usually small, the time complexity is of the order of [Big Theta]: `O(n)`

.

- Worst Case

The worst-case time complexity is [Big O]: `O(n)`

.

- Best Case

The best-case time complexity is [Big Omega]: `O(n)`

. It is the same as the worst-case time complexity.

### Space Complexity

Space Complexity for the radix sort algorithm is `O(n+b)`

, where `b`

is the range of input. It comes from `count`

&`output`

arrays in the radix sort. Sometimes b can be larger than n, making complexity non-linear.