How to Choose the Right Pivot for Your Partition

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