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.
