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!

• Twitter: @rustaceanfm
• Discord: Rustacean Station
• Github: @rustacean-station
• Email: hello@rustacean-station.org

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