I tried merge sort.

and stable_sort() bt both gives TLE. plz help.links to my submission is given.

Merge sort is a Comparison based sort and runs in O(n logn ) time. The question is designed in such a way that the counting Sort algorithm which is O(N) can be easily applied here.All numbers are between 0 and 1000000 so you can count the number of times each digit occurs and print it accordingly. I would suggest you look at a sample solution and read from Wikipedia about counting sort.

I remember that for that problem I used the built-in heapsort() C++ function and got accepted

Also, afaik, sorting doesn’t need to be stable!

This was my accepted solution with heapsort():

In fact, experimenting pretty fast using the built-in sort() function, gets AC in even less time in C++:

Just for fun and training, I’ve also implemented my own version of heapsort in C and got AC as well:

Own implementation of Heapsort

Hope this helps,

Bruno

Do NOT use `cin`

and `cout`

yup as @betlista says…use faster io like…scanf and printf…O(n*logn) passes…it is the IO that causes the TLE!!!