Turbo Sort (TSORT)- Solution with hints

Hint 1:

Click to view

How will you write natural numbers from 1 to N in non-decreasing order? Now suppose you want to repeat some numbers in this series. E.g. - You want to write natural numbers from 1 to 5 and you want to repeat 2 - 3 times, and 4 - 2 times. How will your series look like?

Hint 2:

Click to view

Now suppose you are given a list of integers(say A) in any order. Can you determine how many times natural numbers from 1 to K appear in A? In other words, can you determine how many times 1 appears in A, and then how many times 2 appears in A and so on till how many times K appears in A.
Refer to this

Can you use this information to actually display the numbers in non-decreasing order? What will you choose for the value of K?

Hint 3:

Click to view

How to determine what should be the value of K. Notice that the maximum integer in the list A is 10^6. (Given in the constraints). Now, we know that any number in the list will be between 1 to 10^6. So, if we choose the value of K as 10^6, will it work?

Hint 4: (full solution)

Click to view

Once you know how many times, 1 is repeated in the given list of integers(it may be zero). Let us say 1 is repeated k times. Then you can print 1 k times. Moving on, you know how many times 2 is repeated in the given list of integers. You can print 2 those many times. And so on. If you repeat this process till K. Will you get the numbers in non-decreasing order.

//