Optimal Bounds for Noisy Sorting

Yuzhou Gu, Yinzhan Xu

Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that $(1\pm o(1))n{\log }_{2}n$ comparisons are both necessary and sufficient to sort…