Sorting Algorithms: Speed Is Found In The Minds of People
summary
Examines crisp, measured tweaks to sorting for hundreds‑element arrays: binary insertion cuts comparisons but loses time due to branch mispredicts; branchless binary is slower; a middle‑out insertion and a contrarian stupid small sort (make a heap then run unguarded insertion) reduces comparisons ~9%, moves ~20% and yields up to ~4% wall‑time win at threshold 63 on Intel tests, with huge wins on some inputs (random 0/1 ~25%). Proposes a composite metric (compares + moves + avg access distance) and argues for type introspection/user attributes to pick thresholds.
AI-written summary · about
chapters (18)
- 0:00Intro
- 3:30Quicksort
- 4:43Heapsort
- 7:12Early stopping
- 10:00Sorting small arrays
- 12:53Optimistic insertion sort
- 14:29Binary insertion sort
- 16:39Predictability and entropy
- 18:20Branch prediction is powerless
- 18:57Branchless binary search
- 24:12Try silly things
- 25:05Stupid insertion sort
- 27:50Unguarded insertion sort
- 30:48The gambit
- 32:25Floyds algorithm
- 35:51Push heap
- 46:11Weird territory
- 52:21Random data
related talks
01h 04mBetter Code: Data Structures
01h 00mMoving Faster: Everyday efficiency in modern C++
01h 00mThe Fine Details Behind C++ Containers And Algorithms
05mC++ Sorting Pitfalls, UB & Type Conversion Explained
58mRefresher on Containers, Algorithms and Performance
44mC++ Performance and Optimisation
47mFantastic Algorithms and Where To Find Them
56mBeginners Guide to C++'s Best Kept Secret -- std::algorithm