### 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.

•
• +6
•

 » 9 months ago, # |   +3 There are times when problems have anti-qsort cases, which is mostly just a big problem for java. One of these is the div3c problem Less or Equal: https://codeforces.com/contest/977/problem/C
•  » » 9 months ago, # ^ |   0 Thanks :)
 » 9 months ago, # | ← Rev. 12 →   +7 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)).
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 Thanks :) Btw dmkozyrev can you explain that how std::sort in c++ is smart. Like how does it know when to use heap sort and when to use quick sort.
•  » » » 9 months ago, # ^ |   +9 I'm pretty sure its quicksort until recursion gets too deep it switches to heapsort.And why it's "smart" is because it's been constant optimized and combines two algorithms in an effective way. It's hard to get faster than stl sorting. This hybrid of heap and quick sort is called "introsort" you can find it on wikipediaAnd stable_sort does "timsort" which is constant optimized mergesort by combining insertion sort with mergesort.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +6 in addition, merge sort uses the minimal number of comparisons in the worst case among all sorting algorithms based on comparison. If compare two elements very difficult operation, always use merge sort.
 » 9 months ago, # |   0 Thanks a lot :) It was very helpful.