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