willy108's blog

std::stable_sort vs std::sort
By willy108, history, 4 years ago, In English

This is my first blog post, so it probably will end up being scuffed.

==============================

The problem

So I was working on CF 472D, Design Tutorial: Inverse the Problem and it requires an MST (sorry for spoiling) and I chose to use Kruskals MST to do this (just note that I could've avoided this issue by using any other MST alg, but that's not the point here). So I just coded vanilla Kruskals where I std::sort'ed the edges and used a DSU with path compression and union by size. And I submitted the code and lo and behold, it was TLE on tc 39! I entered into a state of depression and decided to change my std::sort to std::stable_sort and wow, it ac'ed (with 1934ms on a 2 second TL)! Well I was talking some people on Discord later and I this up and one of them told me that the only reason std::sort was slow was since I had used c++11 (which I did) instead of c++17 where std::sort was upgraded. So I submitted it again with std::sort and c++17 and yay it passed (with 1466ms)! and ~470ms faster than my last submission! But to satisfy my curiosity I submitted it again with c++17 and std::stable_sort and woah, it passed with 1154ms, some 310ms faster than the last one.

Please do not judge my template/coding style as that is not the point here, but if you look at my code, the only differences between the submissions are the submission settings and a different sort on line 65 (or the second line of the kruskals function).

the submissions from each correlate to:

  • 1154ms, c++17 with stable_sort

  • 1466ms, c++17 with sort

  • 1934ms, c++11 with stable_sort

  • TLE tc 39, c++11 with sort

also note I did not benchmark memory since that was not something that bothered me in all of this

===============================

The resolution?

So here is one (of probably very few) situations where std::stable_sort outperformed std::sort. The problem that I have right now is that I do not want to miss a submission in a future contest over which sort I chose, since there are definitely problems out here where this problem cannot be avoided by something just as simple as using Prim instead of Kruskal.

If anyone has a good suggestion of which to use (std::stable_sort or std::sort) or a simple impl of a sorting alg that I can write up a little more time for similar results, please link it. I will probably just end up using stable_sort from now on since that was what made a difference here unless there is a really convincing argument or implementation that'll make me switch. No upvoting is needed (unless you want to :D), I just need the help. Thanks for reading and I apologize for any typos, unclear sections, and overall scuffedness.

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

orzzzz

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

From my experience, I think std::sort uses Introsort, while std::stable_sort uses mergesort, which might impact the runtime. The worst case complexity of std::stable_sort is $$$O(n \log^2n)$$$, but is sped up to $$$O(n \log n)$$$ if enough extra memory is available. It's usually better to use std::sort imo, since its worst case complexity is $$$O(n \log n)$$$ without having to hog up any memory, but there are some cases where std::stable_sort is the right choice, since it preserves the relative order of elements in the container.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    A clean (and quite common) trick that people use for stable sorting is to just make a vector of pairs $$$\{ a[i], i \}$$$ for each $$$i$$$, and then sort it in lexicographical order. As a bonus, you get indices of each element too (and you can treat this as a low-powered std::map without insertions/deletions by using binary search, which is usually faster than the usual std::map due to the small constant factor).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Isn't it the same as normal sort? If $$$i < j$$$ and $$$a[i] = a[j]$$$, then $$$(a[i], i)$$$ comes before $$$(a[j], j)$$$ due to lexicographical order

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

        std::sort doesn't guarantee that relative ordering of equal elements is preserved, i.e., if two elements $$$a[i]$$$ and $$$a[j]$$$ are equal in the original array, with $$$i < j$$$, then it might be the case that $$$a[i]$$$ is moved to a location which is ahead of $$$a[j]$$$.

        One possible case where this difference can be made more apparent is the following:

        Suppose you have a vector of lowercase strings such that for each letter $$$L$$$ from $$$a$$$ to $$$z$$$, the subsequence of strings whose first letter is $$$L$$$ is in sorted order.

        The objective is to sort all the strings in order.

        Suppose your comparator function merely compares the first elements of strings. std::stable_sort would give you the correct answer, while std::sort won't, while the trick I mentioned above would behave like std::stable_sort.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

std::sort use more comparison operations than std::stable_sort. Use std::sort if you have vector of ints, std::stable_sort for more complex structure. You can check the number of comparisons with custom comparator. Also you can watch this video https://www.youtube.com/watch?v=kPRA0W1kECg (I can't guarantee that values in the video are correct)

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

    Thank you that helps a lot. I remember afterward modifying my code for Kruskals so that I sorted with a custom comparator that only compared edge weights without caring for the edge endpoints attached with it and only then did std::sort outperform std::stable_sort. std::sort submission vs std::stable_sort submission (1138ms vs 1200ms) and both with the new comparator. I did not include this in the blog post since I didn't realize that that was something worth noting, but with your explanation that makes a lot more sense.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    It's also good to know that (at least from my experience), the differences between std::stable_sort and std::sort start getting significant in geometry problems. For example, sorting by angle (complex comparator) is significantly faster when doing std::stable_sort than std::sort because comparisons are more of a bottleneck than cache friendliness, and memory accesses. Sadly, most implementations of sorting algorithms are benchmarked on arrays of integers, so few are optimized for fewest comparisons.

    → Reply