# LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization

arXiv: https://arxiv.org/abs/2307.08637 · HTML: https://mlsanity.com/paper/2307.08637/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 17 Jul 2023.

## Builds on (most cited first, 21 of 21)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [The Case for Learned Spatial Indexes](https://mlsanity.com/paper/2008.10349/) (2020)
- [A Critical Analysis of Recursive Model Indexes](https://mlsanity.com/paper/2106.16166/) (2021)
- [Bounding the Last Mile: Efficient Learned String Indexing](https://mlsanity.com/paper/2111.14905/) (2021)
- [Towards Practical Learned Indexing](https://mlsanity.com/paper/2108.05117/) (2021)
- [LISA: Towards Learned DNA Sequence Search](https://mlsanity.com/paper/1910.04728/) (2019)
- [Vectorized and performance-portable Quicksort](https://mlsanity.com/paper/2205.05982/) (2022)
- [Parallel String Sample Sort](https://mlsanity.com/paper/1305.1157/) (2013)
- [BlockQuicksort: How Branch Mispredictions don't affect Quicksort](https://mlsanity.com/paper/1604.06697/) (2016)
- [Quicksort with median of medians is considered practical](https://mlsanity.com/paper/1608.04852/) (2016)
- [Histogram Sort with Sampling](https://mlsanity.com/paper/1803.01237/) (2018)
- [Engineering Faster Sorters for Small Sets of Items](https://mlsanity.com/paper/1908.08111/) (2019)
- [Engineering In-place (Shared-memory) Sorting Algorithms](https://mlsanity.com/paper/2009.13569/) (2020)
- [Pattern-defeating Quicksort](https://mlsanity.com/paper/2106.05123/) (2021)
- [Defeating duplicates: A re-design of the LearnedSort algorithm](https://mlsanity.com/paper/2107.03290/) (2021)
- [Using Learned Indexes to Improve Time Series Indexing Performance on Embedded Sensor Devices](https://mlsanity.com/paper/2302.03085/) (2023)

## Abstract (arXiv)

This work analyzes and parallelizes LearnedSort, the novel algorithm that sorts using machine learning models based on the cumulative distribution function. LearnedSort is analyzed under the lens of algorithms with predictions, and it is argued that LearnedSort is a learning-augmented SampleSort. A parallel LearnedSort algorithm is developed combining LearnedSort with the state-of-the-art SampleSort implementation, IPS4o. Benchmarks on synthetic and real-world datasets demonstrate improved parallel performance for parallel LearnedSort compared to IPS4o and other sorting algorithms.