A little order
summary
Benchmarks on http://quick-bench.com/ using Google Benchmark compare std::sort, std::partial_sort, nth_element and custom approaches; claim: for median-like cases a copy+std::sort can beat std::partial_sort, but for small fixed k partial_sort wins, sometimes 10x faster for k≈100 inside million-sized vectors. Charts show how performance changes with k and N, and investigate GCC/Clang/MSVC and libstdc++/libc++ behavior. Slides and commented code live at https://meetingcpp.com/mcpp/slides so the exact numbers and inputs can be reproduced. median vs top-k
AI-written summary · about
chapters (9)
- 0:00Introduction to benchmarking
- 2:47Analyzing sorting algorithms
- 7:44Performance unexpected results
- 9:33Complexity and standards
- 14:45Deeper benchmark investigation
- 21:02Sorting algorithm mechanics
- 26:00Intro sort implementation
- 32:52Selection and heap select
- 37:10Conclusion and Q&A
related talks
57mA Long Journey of Changing std::sort Implementation at Scale
59mBetter Algorithm Intuition
01h 01mWant fast C++? Know your hardware!
48m[a bit noisy] Optimizing Generic Algorithms
01h 05mTaming the performance Beast
30mOptimising stable sort in Rust and mostly failing
01h 00mSTL Features And Implementation Techniques
01h 02mBack to Basics: Almost Always Vector