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](https://codeforces.net/contest/472/problem/D) 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](https://codeforces.net/contest/472/submission/109422457)! I entered into a state of depression and decided to change my std::sort to stable sort and wow, it ac'ed ([with 1934ms on a 2 second TL](https://codeforces.net/contest/472/submission/109422545))! 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](https://codeforces.net/contest/472/submission/109422735))! 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](https://codeforces.net/contest/472/submission/109423213) 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.↵
↵
==============================↵
The problem↵
==============================↵
↵
So I was working on [CF 472D, Design Tutorial: Inverse the Problem](https://codeforces.net/contest/472/problem/D) 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](https://codeforces.net/contest/472/submission/109422457)! I entered into a state of depression and decided to change my std::sort to stable sort and wow, it ac'ed ([with 1934ms on a 2 second TL](https://codeforces.net/contest/472/submission/109422545))! 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](https://codeforces.net/contest/472/submission/109422735))! 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](https://codeforces.net/contest/472/submission/109423213) 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.↵
