# Defeating duplicates: A re-design of the LearnedSort algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2021.

## Built on by (most cited first, 1 of 1)

- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)

## Abstract (arXiv)

LearnedSort is a novel sorting algorithm that, unlike traditional methods, uses fast ML models to boost the sorting speed. The models learn to estimate the input's distribution and arrange the keys in sorted order by predicting their empirical cumulative distribution function (eCDF) values. LearnedSort has shown outstanding performance compared to state-of-the-art sorting algorithms on several datasets, both synthetic and real. However, given the nature of the eCDF model, its performance is affected in the cases when the input data contains a large number of repeated keys (i.e., duplicates). This work analyzes this scenario in depth and introduces LearnedSort 2.0: a re-design of the algorithm that addresses this issue and enables the algorithm to maintain the leading edge even for high-duplicate inputs. Our extensive benchmarks on a large set of diverse datasets demonstrate that the new design performs at much higher sorting rates than the original version: an average of 4.78x improvement for high-duplicate datasets, and 1.60x for low-duplicate datasets while taking the lead among sorting algorithms.