# Optimal Bounds for Noisy Sorting

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2023.

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

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Optimizing Algorithms From Pairwise User Preferences](https://mlsanity.com/paper/2308.04571/) (2023)
- [Sharp Noisy Binary Search with Monotonic Probabilities](https://mlsanity.com/paper/2311.00840/) (2023)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits](https://mlsanity.com/paper/2503.00273/) (2025)
- [Noisy Computing of the mathsfOR and mathsfMAX Functions](https://mlsanity.com/paper/2309.03986/) (2023)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [BlitzRank: Principled Zero-shot Ranking Agents with Tournament Graphs](https://mlsanity.com/paper/2602.05448/) (2026)

## Abstract (arXiv)

Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that (1± o(1)) nlog2 n comparisons are both necessary and sufficient to sort a list of n elements. In this paper, we study the Noisy Sorting problem, where each comparison result is flipped independently with probability p for some fixed p∈ (0, frac 12). As our main result, we show that (1± o(1)) left( frac1I(p) + frac1(1-2p) log2 left(frac1-ppright) right) nlog2 n noisy comparisons are both necessary and sufficient to sort n elements with error probability o(1) using noisy comparisons, where I(p)=1 + plog2 p+(1-p)log2 (1-p) is capacity of BSC channel with crossover probability p. This simultaneously improves the previous best lower and upper bounds (Wang, Ghaddar and Wang, ISIT 2022) for this problem. For the related Noisy Binary Search problem, we show that  (1± o(1)) left((1-δ)fraclog2(n)I(p) + frac2 log2 left(frac 1δright)(1-2p)log2left(frac 1-ppright)right)  noisy comparisons are both necessary and sufficient to find the predecessor of an element among n sorted elements with error probability δ. This extends the previous bounds of (Burnashev and Zigangirov, 1974), which are only tight for δ = 1/no(1).