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²).