  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.

Data Structures and Algorithms