Optimal Bounds for Noisy Sorting

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, 1/2). As our main result, we show that (1± o(1)) ( 1/I(p) + 1/(1−2p) log2 (1−p/p) ) 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.