CppCon 2018: Fred Tingaud “A Little Order: Delving into the STL sorting algorithms”

—
—
—
Benchmarking STL sorting algorithms can lead to surprises. For example, std::partial_sort takes considerably more time to sort half a vector than std::sort to sort it completely...
Starting from this counter-intuitive result, we'll engage on a journey where we'll look at the standard, read implementations of the STL and benchmark code to understand how std::sort, std::nth_element and std::partial_sort are implemented and why. In the process, we'll see some of the challenges STL implementers encountered and how they chose to overcome them.
This session is targetted at STL users who are curious to know how their tool are working.
—
Fred TINGAUD, Development, Murex S.A.S
—

*-----*
*-----*

[kmhofmann]

So, if I understand it correctly, the graph on slide 51 would look different if k is very small compared to N. See also slide 45. We know both k and N when calling std::partial sort. Can't std::partial_sort be tuned to simply revert to (std::nth_element + std::sort) in cases where conditions aren't favorable, i.e. when k is a sizable fraction of N?

[zhaoli]

It will be great to add timsort as std::adaptive_sort

[MrSamkots]

Interestingly, on slide 36 @ 9:55 VS2017 implementation has stable_sort() slightly faster than sort()!