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
std::sortin C++ is very smart:O(n log(n)), large constantO(n log(n)), small constantFor speedup use
std::random_shufflebeforestd::sortAlso, you can use
std::stable_sort,O(nlog(n))time andO(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_sortworks in 4 times faster thenstd::sort. Solution withstd::sortgets TLE, solution withstd::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 length10^5in lexicographical order. It can be solved with sorting (compare substrings with hashes) inO(nlog(n)^2)(easy) or suffix structures (hard) inO(nlog(n)).Thanks :) Btw dmkz 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.