**Problem Link** :–

**Author** :- Ranjan Kumar

**Editorialist** :- Ranjan Kumar

**Difficulty**

medium

**Pre-Requisites** :

sorting, queue.

**Problem Statement** :-

The problem is to sort **N** non-negative random numbers in non -decreasing order using **Radix Sort Technique**.

**Detailed Approach** :–

As the question is very straight forward and standard one, it will be the best to put the standard explanation for the question and not putting my own idea.

So I am putting the approach stated by Geeks For Geeks (which is also mentioned in the question).

**Operations which are performed in Radix Sort is as follows**:-

**1)** Do following for each digit i where i varies from least significant digit to the most significant digit.

………….**a)** Sort input array using counting sort (or any stable sort) according to the i’th digit.

**Example**

Original Unsorted List

170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit **(1s place)** gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]

170, 90, 802, 2, 24, 45, 75, 66

Sorting by next digit **(10s place)** gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]

802, 2, 24, 45, 66, 170, 75, 90

Sorting by most significant digit **(100s place)** gives:

2, 24, 45, 66, 75, 90, 170, 802

Hence we get a sorted sequence for the corresponding random sequence.

**Time Complexity** :–

**O(N*K)**

where **N** - Size of array.

**K** - Number of digits in the largest number.

**Solution** :–

Setter’s Solution can be found here

**Feel free to post comments if anything is not clear to you.**