Radix sort is a linear sorting algorithm that is also called bucket sort. It uses the concept of sorting names in alphabetical orders.

The Quick Sort, Merge Sort, Heap Sort and Selection Sort are comparison based algorithms. But the radix sort is not comparison based algorithm. It is linear sorting and best than comparison sorting.

Suppose n is the number of element in an array.

``````Best Case Time Complexity - O(n)
``````

Suppose the input array is -

``12, 72, 28, 69, 34, 101, 134``

As per radix sort algorithm, first sort the array according to the one's digit.

``````12, 72, 28, 69, 34, 101, 134
0:
1: 101
2: 12, 72
3:
4: 34, 134
5:
6:
7:
8: 28
9: 69``````
``````So, the array becomes -
101, 12, 72, 34, 134, 28, 69``````

Again sort the array according to the ten's digit.

``````101, 12, 72, 34, 134, 28, 69
0: 101
1: 12
2: 28
3: 34, 134
4:
5:
6: 69
7: 72
8:
9: ``````
``````So, the array becomes -
101, 12, 28, 34, 134, 69, 72``````

Again sort the array according to the hundred's digit.

``````101, 12, 28, 34, 134, 69, 72
0:
1: 101, 134
2:
4:
5:
6:
7:
8:
9: ``````
``````So, the array becomes -
12, 28, 34, 69, 72, 101, 134``````

## Radix Sort Program in C

``````#include<stdio.h>

int main()
{
int i, n, a;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("Enter %d numbers : \n",n);
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
printf("\n Sorted numbers using Radix Sort : \n");
for(i = 0; i < n; i++)
printf("  %d",a[i]);
printf("\n");
return 0;
}

int getMax(int a[], int n)
{
int max_value = a, i;
for(i = 1; i < n; i++)
{
if(max_value < a[i])
max_value = a[i];
}
return max_value;
}
{
int bucket, bucket_count;
int i, j, k, remainder, NOP=0, divisor=1, large, pass;
large = getMax(a, n);
printf("\n Largest element : %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}
for(pass = 0; pass < NOP; pass++)
{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}

i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
printf("\n PASS %d :\n",pass+1);
for(i = 0; i < n; i++)
printf("  %d",a[i]);
printf("\n");
}
}
``````

### Output of the above program :

``````Enter the number of elements: 10
Enter 10 numbers :
09
23
15
52
142
163
12
15
62
72

Largest element : 163

PASS 1 :
52  142  12  62  72  23  163  15  15  9

PASS 2 :
9  12  15  15  23  142  52  62  163  72

PASS 3 :
9  12  15  15  23  52  62  72  142  163

Sorted numbers using Radix Sort :
9  12  15  15  23  52  62  72  142  163
``````