Glidesort with Orson Peters

Allen Wyma talks with Orson Peters (orlp.net), creator of the Glidesort (github.com/orlp/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 (twitter.com/rustaceanfm)

• Discord: Rustacean Station (discord.gg/cHc3Gyc)

• Github: @rustacean-station (github.com/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: twitter.com/AerocityMusic

Audio Editing: Plangora (twitter.com/plangora)

Hosting Infrastructure: Jon Gjengset (twitter.com/jonhoo)

Show Notes: Plangora (twitter.com/plangora)

Hosts: Allen Wyma (twitter.com/allenwyma)