Both should run in O(n log n), but in general sort is faster than stable_sort. How big is the performance gap in practice? Do you have some experience about that?
I want to sort a very large number of structs that have a size of about 20 bytes. The stability of the result would be nice in my case, but it is not a must. At the moment the underlying container is a plain array, perhaps it could be changed to a std::deque later on.
As it is trivial to replace one algorithm with the other, why don't you try them both and time the results?
Big enough to warrant a separate function that does stable sort and not have std::sort() do it transparently.
According to the STL documentation, stable_sort() performs between NlogN comparisons when sufficient memory is available. When insufficient memory is available, it degrades to N((logN)^2) comparisons. Therefore it is roughly of the same efficiency as sort() (which performs O(NlogN) comparisons in both average and worst case) when memory is available.
For those interested, sort() uses an introsort (quicksort which switches to heapsort when the recursion reaches a certain depth) and stable_sort() uses a merge sort.
How big is the performance gap in practice? Do you have some experience about that?
Yes, but it didn't go the way you would expect.
I took a C implementation of the Burrows-Wheeler Transform and C++-ified it. Turned out a lot slower than the C code (though the code was cleaner). So I put timing instrumentation in there and it appeared that the qsort was performing faster than the std::sort. This was running in VC6. It was then recompiled with stable_sort and the tests ran faster than the C version. Other optimisations managed to push the C++ version ~25% quicker than the C version. I think it was possible to eke more speed but the clarity of the code was disappearing.
Sometimes std::stable_sort() is needed because it maintains order of elements that are equal.
And the conventional advice is that, if maintaining order is not important, you should use std::sort() instead.
However, its context dependant. There is plenty of data that is best sorted with stable sort even if you don't need to maintain order:
Quicksort quickly becomes worst-case performance if the data has consistently poor pivot points.
The Burrows-Wheeler Transform is an algorithm used as part of data compression, e.g. bzip2. It requires sorting all the rotations of the text. For the majority of text data, merge sort (as often used by std::stable_sort()) is substantially faster than quicksort (as usually used by std::sort()).
bbb is a BWT implementation that notes the advantages of std::stable_sort() over sort() for this application.