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:
Hope this helps,
Do NOT use
yup as @betlista says…use faster io like…scanf and printf…O(n*logn) passes…it is the IO that causes the TLE!!!