Optimal Bounds for Noisy Sorting

Sorting is a fundamental problem in computer science. In the classical setting, it is wellknown that (1 ± o(1))n log 2 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, 1 2 ). As our main result, we show that

noisy comparisons are both necessary and sufficient to sort n elements with error probability o(1) using noisy comparisons, where I(p) = 1 + p log 2 p + (1p) log 2 (1p) 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

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/n o(1) .