Noisy Sorting Capacity

Ziao Wang, Nadim Ghaddar, Banghua Zhu +1

Sorting is the task of ordering $n$ elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the…