Sorting with Predictions
Xingjian Bai Christian Coester
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
\eta_i)$ exact comparisons, where $\eta_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.