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 data). http://www.cplusplus.com/reference/algorithm/stable_sort/ 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. http://www.cplusplus.com/reference/algorithm/sort/ 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? REPOSITORY R241 KIO REVISION DETAIL https://phabricator.kde.org/D10857 To: jtamate, #frameworks, dfaure, markg Cc: markg, apol, michaelh
