simply sort it

smone plz… tell an effeftive algo for TSORT
BEST SOLUTIONS R DIFFICLT 2 UNDERSTAND… :frowning:

I expect, that you mean this problem

Well you just need to sort array of elements. But the number of elements is too big for classic solutions like Quicksort or Mergesort.

You can use fact, that each element is smaller than 10^6. Just create array A of length 10^6 at begining each element is zero.

Than read input and when you read number x just increase element A[x]. This means, that after reading whole input in array A you get for each number x number of times, this element occures in input.

At the end just proces whole array A from 0 to 1000000 and write number x A[x] times. You will get correct output.

I hope this explanation is clear enough.

This sorting method is also know as Countsort. Is very easy to implement and have optimal time complexity O(n). But is usable only, when elements we sorting are reasonably small.

Hello,

Well, if you really want to get AC and you are using C/C++, you can do it pretty simply by calling any built-in sorting function like QuickSort or HeapSort…

If you really want to take the time to implement a good sorting algorithm yourself, well, I implemented HeapSort in C and got AC…

Always keep in mind that on this particular problem, the key idea is sorting many items as fast as possible, so, if you focus your attention on sorting algorithms solely, you will be able to grasp solutions better :slight_smile:

Best regards and I hope this helped,

Bruno

Along with efficient sorting algorithm also have a look at fast I/O methods as amount of data is huge.