“A Little Order: Delving into the STL sorting algorithms”
summary
Benchmarks on Quick‑Bench and local compilers show finding the median of a 1,000,000 element vector with std::nth_element plus std::sort is three times faster than std::partial_sort for that case. Tests repeat across GCC, libc++ and MSVC, varying N and k. Analysis of STL source shows partial_sort is implemented with heap_select followed by heapsort and is tuned for very small k, while nth_element uses introselect (quickselect then heapselect) so complexity and pivot behavior explain the counterintuitive timings. Use partial_sort for tiny k in huge N, otherwise prefer nth_element + sort.
AI-written summary · about
chapters (10)
- 0:00Introduction to STL sorting
- 1:07Sorting algorithms overview
- 5:23Investigating performance differences
- 9:25Testing with multiple compilers
- 10:31Benchmarking with varying sizes
- 14:08When to use partial_sort
- 14:32Diving into the code
- 19:00Introsort and insertion sort
- 21:52Understanding partial_sort
- 25:27Key takeaways and conclusion
related talks
46mComparison is not simple, but it can be simpler
47mHow the JVM Optimizes Generic Code - A Deep Dive
56mThrowing Tools at Ranges
01h 00mBuilding and Extending the Iterator Hierarchy in a Modern, Multicore World
01h 03mstd::midpoint? How Hard Could it Be?
57mHow To Implement the C++ Standard Library - (Part 1 of 2)
38mWhat's New In C++23
14mFast Linear Programming through Transprecision Computing on Small and Sparse Data