Radix Sort Algorithm in Data Structure

Radix Sort can be used to sort a list of elements.

Algorithm for Radix Sort:

Algorithm fnRadix(P, n)
{
div=1;
num= number of digits in the largest number of the array P[];
for(pass=1; pass<=num; pass++)
{
for(k=0; k<10; k++)
buck[k]=0;
for(i=0; i<n; i++)
{
j=(P[i]/div)%10;
bucket[j][buck[j]++]=P[i];
}
i=0;
for(k=0; k<10; k++)
{
for(j=0; j<buck[k]; j++)
P[i++]=bucket[k][j];
}
div*=10;
}
} // End of Algorithm

Time complexity of Radix Sort:

Radix sort is dependent on three things:

F(N)=R*D*N

Where R=Radix (10 for decimal, 26 for alphabets and 2 for binary)
D = Number of digits in the largest element.
N = Size of an array of elements.

1. Base Case: In the best case, the number of digits in largest element (D) will be log_RN. So, the maximum number of comparisons = R*log_RN*N Which is of O(N log N).

2. Worst Case: Suppose the number of digits in the largest element (D) is equal to the number of elements in the array(N) which is of O(N²).