Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

When does std::stable_sort outperform std::sort?

Revision en2, by brdy, 2018-01-18 02:31:12


I was doing this problem and was getting TLE on the last two test cases.

On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.

According to this benchmark, stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.

In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.

You can try to submit my solution and it should AC. But if you replace "stable_sort" with "sort" it will TLE.

Does anyone know which types of cases stable_sort can outperform sort?

Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.

Tags stable_sort, sort, sortings, gotem


  Rev. Lang. By When Δ Comment
en2 English brdy 2018-01-18 02:31:12 173
en1 English brdy 2018-01-18 00:33:02 1015 Initial revision (published)