What is the Radix Sort Algorithm in Data Structures | Data Structures Tutorial

In this article, you will understand the Radix sort Algorithm in better detail.

Radix sort is a sorting algorithm that is used in sorting the elements by first grouping every digit of the same place value. Afterward, sort the elements according to their increasing/decreasing order. 

Assume an array of 8 elements. We have to sort the elements based on the value of the unit place. Now, we will sort the elements based on the value of the tenth place. This process goes on until the last significant index. In this counting, sort is used as an intermediate sort in the radix sort. 

Working on Radix Sort

1. Find the max element in the array, and call it max. Let Y be the number of digits in max. Y is calculated because we have to go through all the significant indexes of all elements. 
2. Go through each particular index one by one. Use any particular sorting techniques to sort the digits at each significant index. We use counting sort for this. Sort the elements based on the unity place digits (X=0).
3. In this., sort the array elements on digits at tens place. 
4. Finally, sort the elements of the array based on the digits at the hundreds place. 

Radix Sort Algorithm

radix_sort(array)

   d <- find the maximum number of elements in the largest element

   create d buckets of size 0-9

   for i <- 0 to d

      sort the array elements according to ith place digits using counting_sort

counting_sort(array, size)

    large <- figure maximum value element in the array

    initialize count array with all zeros

    for i <- 0 to size

        put the total count of each unique element and keep the count 

        at ith index in count array

   for j <- 1 to large

        find the cumulative sum and keep it in count array i.

   for j <- size to 1

        restore the elements to the array until the count is decreased to 1.

Complexity

Time complexity

The best case complexity is O(n+k), the average case complexity is O(n+k), and the worst case complexity is O(n+k). 

Space complexity is O(max)

Radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.

Applications of Radix Sort Algorithm

• It is used when using the DC3 algorithm while making a suffix array.
• It is used in the implementation of places where there are numbers in large ranges.