brdy's blog

When does std::stable_sort outperform std::sort?
By brdy, history, 7 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +6 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Really strange...

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply