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.

通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种“快速但不精确”的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用O(Σi log ηi)个精确比较，其中ηi是第i个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从O(n)平滑地降低到O(nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

基于预测的排序