Let us have n records with integer keys in the range of O n2

Let us have n records with integer keys in the range of [O, n²).

Please explain how to insert the keys so that Radix Sort will only take O(n) time to sort n records.

Schedule

Solution

Suppose you have n records with integer keys in range as given above then it is possible to insert keys in such a manner that time complexity of radix sort will be of O(n) at the time of sorting. So what to do at the point of insertion let me explain:

So if we insert elements in sorted manner by using counting sort at indexes Radix sort will automatically give O(n) time as time complexity.