Allen Wyma talks with Orson Peters, creator of the Glidesort sorting algorithm that may make its way into the Rust core library.
Contributing to Rustacean Station
Rustacean Station is a community project; get in touch with us if you’d like to suggest an idea for an episode or offer your services as a host or audio editor!
Timestamps
- [@0:00] - Introduction to Glidesort
- [@1:19] - What got Orson interested in sorting algorithms
- [@4:47] - Process of creating Glidesort
- [@6:06] - Quicksort and how to handle low cardinality inputs
- [@8:18] - Three-way comparison and binary partitioning
- [@10:59] - Basic terms to know about quicksort and mergesort
- [@15:28] - Choosing an element as a pivot
- [@24:16] - Stable and unstable sorting algorithms
- [@27:03] - How Glidesort can help with memory usage and memory savings
- [@35:51] - How Glidesort detects if there is already a sorting in an array
- [@38:19] - Linear scanning
- [@41:47] - When Glidesort is a good algorithm to use
- [@45:53] - Glidesort is a comparison-based algorithm
- [@49:09] - What datatype would be great for Glidesort
- [@52:17] - Sorting algorithms and language issues
- [@53:11] - Sorting algorithm in Python vs Rust
- [@55:52] - The challenge of implementing sorting algorithms in Rust
- [@58:36] - Reducing Glidesort’s code size
- [@1:01:21] - Standard library benchmarking criteria
- [@1:02:52] - Performance evaluation of Glidesort and other improvements
- [@1:06:08] - Quantum computing
- [@1:07:43] - Next on the list for Glidesort improvements
- [@1:10:54] - Parting thoughts
Credits
Intro Theme: Aerocity
Audio Editing: Plangora
Hosting Infrastructure: Jon Gjengset
Show Notes: Plangora
Hosts: Allen Wyma