**Radix sort** is a sorting technique which is **different from the concept** of **bubble**, **selection**, **merge **or **quick sort** as **radix sort** is done by **depending on the digits of the elements** from the **right most bit**** to the ****left most bit**** **and by sorting the positional digits the sorting is performed. Unlike the other commonly used sorting algorithms, **radix sort** is a **non-comparison**** based sorting** algorithm. It depends on the place values of the numbers and grouped together according to the place values and thus sorting is performed.

**PROCEDURE WITH EXAMPLE:**

Suppose an array of **7 elements** is taken to perform radix sort as follows:

Now, this array is to be sorted. Before sorting the array the number of **digits in the ****maximum**** ****element** is to be found out. In this case, the **maximum element**** of this array** is **654** and the **number of ****digits**** if this element is ****3**. So the **number of passes** required to sort is **3**.

In the **first pass** the **right most digits**** of the element is considered** and will be **sorted according**** to those digits** and we will get the array as:

After the first pass, the array is **sorted according**** to the ****right most digit** of the elements and the array is:

Now in the **second pass** the **2nd digit**** from the ****right side** will be considered and **will be ****sorted**** according** to those digits underlined in the above array. Now the array will be sorted and the new array will be:

Now, the array is **sorted according to the 2nd digit** (from the right side) of each element of the array.

This is the last pass to sort the elements of the array, so here the array will be **sorted according to the ****most significant bit**** that is the ****left most bit of each element**. The elements which are of 2 digits, for that elements the **3rd bit from the right side is not available**, hence **‘0’ will be considered as the most significant bit** of the elements as follows:

So the **final ****sorted array** will be:

```
INPUT:An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
Step 1: Create a function “void radixsort(int a[],int n)”
Step 1.1: Set or initialise the all elements of an integer type array ‘d’ at 0 i.e
Set d[i] <- 0 [ i= 0 to 9]
Step 1.2: Take the max number of digit in an integer type variable ‘max’ and this is the number of required pass to do the sorting.
Step 1.3: While(pass ≤ max) then repeat Step 1.4 to Step 1.22
Step 1.4: For i=0 to i<n repeat Step 1.5 to Step 1.13
Step 1.5: Set c <- 0
Step 1.6: Set p <- a[i]
Step 1.7: While(c<pass) then repeat Step 1.8 to Step 1.10
Step 1.8: Set r <- p mod 10
Step 1.9: Set p <- p/10
Step 1.10: Set c <- c+1
[End of Step 1.7 ‘While’ loop]
Step 1.11: Set j <- d[r]
Step 1.12: Set b[r][j] <- a[i]
Step 1.13: Set d[r] <- d[r]+1
[End of Step 1.4 ‘For’ loop]
Step 1.14: Set pass <- pass+1
Step 1.15: Set I <- 0
Step 1.16: For j=0 to 9 repeat Step 1.17 to Step 1.20
Step 1.17: If(d[j]>0) then do
Step 1.18: For k=0 to k<d[j] repeat Step 1.19 and Step 1.20
Step 1.19: Set a[i] <- b[j][k]
Step 1.20: Set I <- i+1
[End of Step 1.18 ‘For’ loop]
[End of ‘If’]
[End of Step 1.16 ‘For’ loop]
Step 1.21: For i=0 to 9 repeat Step 1.22
Step 1.22: Set d[i] <- 0
[End of 1.3 ‘While’ loop]
[End of the function “void radixsort(int a[],int n)”]
Step 2: Create the function “void main()”
Step 2.1 Take the number of elements from the user in an integer type variable ‘n’ .
Step 2.2: Take the unsorted elements from the user in an array ‘a’.
Step 2.3: Print the unsorted array.
Step 2.4: Call the function ‘radixsort(a,n)’
Step 2.5: Print the sorted array ‘a’.
Step 2.6: Stop.
[End of the function “void main()”]
Step 3: Stop.
```

__CHARACTERISTICS:__

**1. **It is a **non-comparison** based sorting technique.

**2. **It is performed by performing a multi-pass bucket sort.

**3. **It is a straight sorting algorithm.

**4. **It is not an **in-place** sorting algorithm.

**5. **It is a stable sorting algorithm.

**6. **It is a linear sorting algorithm.

__TIME COMPLEXITY:__

The **best case, average case, and worst-case** complexity are the **same**** in the case of ****radix sort **as it is a non-comparison based sorting technique.

**The time**** complexity of ****radix sort**** is ****O(k.n)**** where ****n**** is ****a ****number of integer elements of word size ****k****.**

__SPACE COMPLEXITY:__

The total **space required to sort** the data is **O(n + k)** where **n ****is the number of elements** and **k ****is the range of data** (or word size).

__APPLICATIONS:__

**1. ****Radix** sorts are used mostly to the collections of binary strings and integers to sort.

**2. **Radix sort can be parallelized or can be implemented in parallel computing easily.

__ADVANTAGES:__

**1. **The sorting is done by straight calculation.

**2. **It is a steady sort.

**3. **The complexity is almost the same as the other sorting algorithms but the calculation in radix sort is simpler than the others.

__DISADVANTAGES:__

**1. **It requires extra spaces for intermediate sort.

**2. **It is less adaptable.

**3. **It is quite complex to program for a wide assortment of usefulness.

**4. **The above algorithm only works for the positive data only as it is sorted according to the place values but the elements are not compared with each other.

**5. **We will get better complexity to compare to comparative sorting but it only true for 32-bit and 64-bit digits numbers. For more digits, it does not give the linear time complexity

Related

- Heap Sort Iterative
- Heap Sort using recursion
- Merge Sort Iterative
- Merge Sort using recursion
- Quick Sort using recursion
- Quicksort Iterative
- Insertion Sort
- Selection Sort
- Bubble Sort
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by