# Radix Sort in Data Structure Radix sort is a sorting technique that isn’t based on comparison and groups the individual digits of the same place value before sorting the items. After that, arrange the items in increasing order or decreasing order. Let’s say we have an array of seven elements. We’ll start by sorting elements by the value of the unit place. Then we’ll sort the elements by the value of the tenth position. This process continues until the last significant location is reached. Elements of an array before applying radix sort are {101, 45, 543, 233, 321, 833, 432}. Our array will like this {101, 321, 432, 543, 233, 833, 45} after sorting the unit place digits. As an intermediate sort, Radix sort uses counting sort.

Let’s start with an example array having elements: [125, 436, 568, 27, 5, 49, 792]. 1. Find the array’s largest element, i.e. max. Let X be the maximum number of digits. Because we must go over all of the significant positions of all elements, X is calculated. In the given array [125, 436, 568, 27, 5, 49, 792], we have the largest number 792. It has 3 digits. Therefore, the loop should go up to hundreds place (i.e., 3 times). 1. Now, go through each important location one by one. Sort the numerals at each significant place using any stable sorting strategy. For this, we applied a counting sort. Sort the elements by the digits in the unit position (X=0). 1. Sort the elements by digits in the tens place now. 1. Finally, sort the elements by the hundreds place digits. Step 1: As Max, find the highest number in ARR.

Step 2: Determine the number of digits in Max and set NOS = number of digits in Max.

Step 3: For PASS = 1; PASS = NOS, repeat Steps 4–8.

Step 4: Repeat Steps 5–7 for ARR sizes I=0 to I.

Step 5: SET DIGIT = Arr[I]

Step 6: At index DIGIT, add element Arr[I] to the sub array.

Step 7: Increase the number of sub arrays in the index DIGIT.

[LOOP ENDS]

Step 8: Using the index 0 as a starting point, choose elements from the sub array and place them in ARR.

[LOOP ENDS]

Step 9: FINISH

## Analysis of Radix Sort for Complexity

### Time Complexity We already know that the Counting sort algorithm takes Θ(n+k) time, where n is the number of elements in the input array and k is the largest element among the dth place elements in the input array (ones, tens, hundreds, and so on). Counting sort is now called inside a ‘for loop’ that runs for d times, where d is the number of digits in the input array’s largest element (max). As a result, we can predict that Radix sort will take Θ(d( n+ k)). As a result, radix sort has a linear time complexity, which is superior to Ω(nlogn) for comparison-based sorting algorithms.

### Space Complexity Radix sort employs Counting sort, which uses auxiliary arrays of sizes n and k, where n is the number of items in the input array and k is the largest element among the {d}^{th} place members of the input array (ones, tens, hundreds, and so on) (note that this is not the largest element of the input array). As a result, the Radix sort has a space complexity of Ω(n+k).  