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