jtamate added a comment.
In D10857#216725 <https://phabricator.kde.org/D10857#216725>, @dfaure wrote:
> I cannot confirm that stable_sort is faster, on the contrary.
http://www.davidfaure.fr/2018/qsort_performance.cpp updated, says (repeatedly)
> "std::sort took: 5003 ms"
> "std::stable_sort took: 7490 ms"
> Maybe on specific data (the actual filenames you're testing this with),
stable_sort ends up being faster, but this isn't true in general (with random
If enough extra memory is available, linearithmic in the distance between
first and last: Performs up to N*log2(N) element comparisons (where N is this
distance), and up to that many element moves.
Otherwise, polyloglinear in that distance: Performs up to N*(log2(N))^2
element comparisons, and up to that many element swaps.
On average, linearithmic in the distance between first and last: Performs
approximately N*log2(N) (where N is this distance) comparisons of elements, and
up to that many element swaps (or moves).
So, std::sort then?
To: jtamate, #frameworks, dfaure, markg
Cc: markg, apol, michaelh