TSORT- TLE.. i tried merge sort and sorting in algorithm header

general
, , , , , ,
1

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

2

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.

3

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

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

This was my accepted solution with heapsort():

Built-in Heapsort

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

Built-in std::sort()

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

4

Do NOT use cin and cout :wink:

1 Like
5

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