Sorting with Predictions. (arXiv:2311.00749v1 [cs.DS])

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 …

algorithms arxiv efficiency explore list prediction predictions sorting through