Sorting with Predictions
This work addresses sorting efficiency for data processing applications by integrating predictions, though it is incremental as it builds on existing learning-augmented algorithm frameworks.
The paper tackles the problem of sorting by using learning-augmented algorithms that leverage predictions to reduce comparisons, achieving optimal complexity of O(∑ log η_i) comparisons, which degrades smoothly from O(n) to O(n log n) as prediction quality worsens.
We explore the fundamental problem of sorting through the lens of learning-augmented algorithms, where algorithms can leverage possibly erroneous predictions to improve their efficiency. We consider two different settings: In the first setting, each item is provided a prediction of its position in the sorted list. In the second setting, we assume there is a "quick-and-dirty" way of comparing items, in addition to slow-and-exact comparisons. For both settings, we design new and simple algorithms using only $O(\sum_i \log η_i)$ exact comparisons, where $η_i$ is a suitably defined prediction error for the $i$th element. In particular, as the quality of predictions deteriorates, the number of comparisons degrades smoothly from $O(n)$ to $O(n\log n)$. We prove that the comparison complexity is theoretically optimal with respect to the examined error measures. An experimental evaluation against existing adaptive and non-adaptive sorting algorithms demonstrates the potential of applying learning-augmented algorithms in sorting tasks.