The Rustacean Station Podcast

Glidesort with Orson Peters

Posted Fri, 05 May 2023 16:46:00 +0000

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