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.

Thanks in advance.

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

Thanks :)

`std::sort`

in C++ is very smart:`O(n log(n))`

, large constant`O(n log(n))`

, small constantFor speedup use

`std::random_shuffle`

before`std::sort`

Also, 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))`

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

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 wikipedia

And stable_sort does "timsort" which is constant optimized mergesort by combining insertion sort with mergesort.

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.

Thanks a lot :) It was very helpful.