Nope. quicksort won’t. Not mergesort as well, if implemented properly. I used the sort function from the algorithm library which uses the quicksort algorithm for large n and nope, it didn’t give TLE. Dont worry it’ll work!
Standard Sorting(C++) - 2.39 s
Merge Sort - 3.11 s
Heap Sort - 3.10 s
Count Sort - 2.33 s
Results posted by someone on comments of the same problem on SPOJ.
My bad Anyway can I see your implementation of Standard sort which was AC on Spoj? What’s the point of solving the question then if you solve with any sorting algorithm (n log n).
Nobody would have used bubble sort, i am sure! If u feel that someone has used bubble sort and still submitted successfully, please comment a link of the solution! Bubble sort can never solve this problem. You atleast require an O(nlogn) technique.
@wrangler00: Hai man! The time complexity of bubble sort is O(n^2) in the worst case and the best case is O(n) if modified. But as a programmer we should always look at the worst case! See here O(n^2) means is that if there are n elements then there should be n^2 comparisons. As far as i know with my limited knowledge in competeive programming if the value of the worst case, here it is n^2 is more than 10^8 then it will surely will not run in 1 second. So here check the question N<=10^6. Taking the worst case if the value of N=10^6, then complexity of your bubble sort is O(n^2) is 10^12 where n=10^6. So going beyond 10^8 it will surely not run in 1 second. Approximately it will take around 30,000+ second. Hope you got the mistake. As pranjalranjan said either you can use Merge Sort or Heap Sort since both the algorithms complexities are O(N Log N). Check by substituting the value of n in the above said complexities. It will fit in 10^8. But for this question the best algorithm is Counting sort, as what kaushik_iiitd said, whose time complexity is linear i.e. O(N). You can google it! If you dont undertand it please do post it here. We will help you! I repeat , this question can be done with quick sort, merge sort, heap sort, i.e any sorting algorithm whose worst time complexity is N Log N or lesser!