LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization
This work addresses the problem of efficient parallel sorting for large datasets, presenting an incremental improvement over existing methods.
The paper analyzed LearnedSort as a learning-augmented SampleSort and developed a parallel version by combining it with IPS4o, showing improved parallel performance on synthetic and real-world datasets compared to IPS4o and other algorithms.
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.