Radix Sort Algorithm Explained with Examples

We are discussing Sorting Algorithms now. If you want, you can refer them too.

1. Sorting Algorithms
2. Counting Sort Algorithm — A brief explanation with an example
3. Counting Sort Algorithm: Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

In this article, we are going to explore a linear sorting technique called Radix Sort.

In our last article, I asked a question.

Point to think : What will happen if the array to be sorted is this? Will you still prefer to use Counting Sort? Why?{10, 50, 100000, 500, 30, 900, 5}

In this array, the elements are in the range of [5,100000]. That is, [1,n²]. This can result in the algorithm going O(n²) which is worse than the worse case of Counting Sorting. We are preferring linear sorting to perform faster than O(nlogn). But here, Counting Sort can go to O(n²). So what shall be done?

In these types of situation we can use Radix Sort!

Radix sort is an integer sorting algorithm that sorts data with integer keys by clustering the keys together based on the individual digits that have the same significant position and value (place value). To sort an array of numbers, Radix sort employs counting sort as a subroutine. Radix sort works on data types other than integers because integers can be used to represent strings (by hashing the strings to integers).