Algorithms
Topics:
• Searching
• Sorting
• Greedy Algorithms
• Graphs
• String Algorithms
• Dynamic Programming

Prerequisite: Counting Sort

QuickSort, MergeSort, HeapSort are comparison based sorting algorithms.
CountSort is not comparison based algorithm. It has the complexity of $O(n+k)$, where $k$ is the maximum element of the input array.
So, if $k$ is $O(n)$ ,CountSort becomes linear sorting, which is better than comparison based sorting algorithms that have $O(n log n)$ time complexity. The idea is to extend the CountSort algorithm to get a better time complexity when k goes $O(n^2)$. Here comes the idea of Radix Sort.

Algorithm:
For each digit $i$ where $i$ varies from the least significant digit to the most significant digit of a number
Sort input array using countsort algorithm according to ith digit.

We used count sort because it is a stable sort.

Example: Assume the input array is:
10,21,17,34,44,11,654,123
Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).
0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

So, the array becomes 10,21,11,123,24,44,654,17
Now, we'll sort according to the ten's digit:
0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

Now, the array becomes : 10,11,17,21,123,34,44,654
Finally , we sort according to the hundred's digit (most significant digit):
0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

The array becomes : 10,11,17,21,34,44,123,654 which is sorted. This is how our algorithm works.

Implementation:

void countsort(int arr[],int n,int place)
{
int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
int output[n];
for(i=0;i<n;i++)
freq[(arr[i]/place)%range]++;
for(i=1;i<range;i++)
freq[i]+=freq[i-1];
for(i=n-1;i>=0;i--)
{
output[freq[(arr[i]/place)%range]-1]=arr[i];
freq[(arr[i]/place)%range]--;
}
for(i=0;i<n;i++)
arr[i]=output[i];
}
void radixsort(ll arr[],int n,int maxx)            //maxx is the maximum element in the array
{
int mul=1;
while(maxx)
{
countsort(arr,n,mul);
mul*=10;
maxx/=10;
}
}


Complexity Analysis:
The complexity is $O((n+b)* log_b(maxx))$ where $b$ is the base for representing numbers and $maxx$ is the maximum element of the input array. This is clearly visible as we make $(n+b)$ iterations $log_b(maxx)$ times (number of digits in the maximum element) . If $maxx \le n^c$,then the complexity can be written as $O(n * log_b(n))$.

1. Fast when the keys are short i.e. when the range of the array elements is less.
2. Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.