Hello,

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.

If you mean the column

`Iterations`

(next to`Time(ns)`

and`CPU(ns`

), then you are misinterpreting the benchmark completely. The column says, how often the benchmark was repeated. Not how many cycles / iterations the algorithm uses. In all tests`std::sort`

was faster than`std::stable_sort`

.Thanks. Do you know any specific case where this is not true? (where stable_sort is faster)

std::sort generally is an Introsort, that first does Quicksort, but might fall back to heapsort (to guarantee worst case O(nlogn) vs O(n^2) of Quicksort). When that fallback happens, it can probably be overall slower than Mergesort (std::stable_sort) from the beginning. Read this for more information on Introsort.

Heapsort and Mergesort have a higher constant factor than Quicksort.

No.

And I also suspect, that in your code

`std::sort`

is not slower than`std::stable_sort`

. I haven't read the problem statement, but from what I can see in you solution is that the complexity is`O(n*m)`

. This will dominate every sort that you do. So maybe it was just a coincidence, e.g. time limit of 1 sec, and the first time you submitted it run in 1.01 sec, and the second time it run in 0.99 sec.I checked it (twice), and indeed the stable_sort version runs in ~1.95s, so pretty close to TL. But for test 8, stable_sort took 1.15s vs sort 1.35s, seems significant. For test 9, stable_sort 1.6s and sort TLE...

Really strange...

Time limits are usually set with reserve. There is probably better solution. Sorting n*m can be avoided as there no more than n+m unique values. You can sort list of lengths and when you take length iterate over all the edges in that row/column.

I've run it multiple times and the stable_sort solution always manages to squeeze right under the time limit.

Also the complexity is nmlog(nm)

Auto comment: topic has been updated by brdy (previous revision, new revision, compare).Generally,

`stable_sort`

implementations make much less comparisons as opposed to`sort`

. It's also possible that`stable_sort`

does less memory moves, but I'm not sure here.