### CreativeAss's blog

By CreativeAss, history, 9 months ago, , Average time of quick sort is O(nlogn). So in many contest n is like 5*10^5 at that time nlogn would be ~10^7 operations. Considering not worst but some bad case the sorting can take around ~(4*10^8 — 5*10^8) operations and give a Time Limit Exceeded.

Now I wanted to know that can this type of case happen during a submission in Codeforces or It can never happen.

Sorry for silly question. Comments (7)
 » 9 months ago, # | ← Rev. 12 →   std::sort in C++ is very smart: in worst case it is heap sort, O(n log(n)), large constant in another case it is quick sort, O(n log(n)), small constant For speedup use std::random_shuffle before std::sortAlso, you can use std::stable_sort, O(nlog(n)) time and O(n) additional memory (it's a merge sort), if you write code in C++, of course.I can give a link on problem where std::stable_sort works in 4 times faster then std::sort. Solution with std::sort gets TLE, solution with std::stable_sort — accepted, it's in russian, but you can use google translate. In this problem, you need to sort all the cyclic shifts of the string length 10^5 in lexicographical order. It can be solved with sorting (compare substrings with hashes) in O(nlog(n)^2) (easy) or suffix structures (hard) in O(nlog(n)).