# Generalized Sorting with Predictions

arXiv: https://arxiv.org/abs/2011.00172 · HTML: https://mlsanity.com/paper/2011.00172/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2020.

## Built on by (most cited first, 5 of 5)

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization](https://mlsanity.com/paper/2302.00928/) (2023)
- [Efficient Portfolio Selection through Preference Aggregation with Quicksort and the Bradley--Terry Model](https://mlsanity.com/paper/2504.16093/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)

## Abstract (arXiv)

Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires tilde O(n3/2) probes. We study this problem with additional predictions for all pairs of allowed comparisons as input. We propose a randomized algorithm which uses O(n log n+w) probes with high probability and a deterministic algorithm which uses O(nw) probes, where w is the number of mistakes made by prediction.