Explore innovative sorting algorithm variants in this 55-minute conference talk by Andrei Alexandrescu at NDC Conferences. Delve into the world of efficient sorting and searching techniques, uncovering less-known but faster "allegro" versions of classic algorithms. Discover surprising insights about modern complex architectures and learn how to optimize performance. Journey through topics such as Quicksort's popularity, Binary Insertion Sort, GNU heapify, and the concept of Average Access Distance. Gain valuable tips on optimization techniques and understand why sometimes trying "silly things" can lead to breakthrough improvements in algorithm efficiency.
Allegro Means Both Fast and Happy - Coincidence
Overview
Syllabus
Intro
Subtitle #2
Sorting
Why is Quicksort Popular?
Challenge
Why Not Binary Insertion Sort?
Tip: Try Silly Things
Net Optimization
GNU heapify
Optimization is Imagination
Inner Loop
Comparisons (baseline: red)
Trying Silly Things
A Helpful Metric
Average Access Distance
Summary
Taught by
NDC Conferences
