A Little Order: Delving into the STL sorting algorithms

Speaker: Fred Tingaud

Audience level: Beginner | Intermediate


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.