How should I implement Sort properly if I have to use it without getting TLE?

I stumbled upon the problem of Chef and Integers (, and thought I’ll give it a try. Now, the algorithm I’ve implemented uses sort. Now this obviously leads to a TLE for large input cases surely but is working otherwise. How should I implement sort to take care of this?

Or the only option there is, is to implement a different algorithm? How should that go about?

@razordude1717 : You are using quicksort which is O(n^2) in worst case . You should use some n log n algorithm for sorting , like merge sort or heap sort .

@razordude1717 >> You can use the C++ std::sort() or std::stable_sort(). That would save your time writing the code snippet to sort in your own code. std::sort() is a kind of hybrid algorithm. More details here


a[5] = {3, 7, 1, 2, 8};    //a sample array
std::sort(a, a+5);         //you can omit the "std::" part if you have already
                           //declared using namespace std

Output will be a sorted array.

@vineetpaliwal: I tried heap sort too, it still is causing TLE. I think it has to do with the algorithm.

@@razordude1717 : You are actually simulating the whole process which will obviously give TLE . You have numbers in the range of -10^9 to 10^9 .

To see the correct algorithm please refer the editorial ,

That should help you . If it is unclear to you , you can ask me here on this thread by tagging your query with @vineetpaliwal

TLE in INTEG is not because of sorting (i suppose you are using some nlog(n) algorithm).
After sorting you are supposed to use some tricky stuffs to reduce time complexity.
I used O(n) after sorting.
You can go through my solution

Ask me on this thread if you have any further queries.