An Optimal Sorting Algorithm for Persistent Random Comparison Faults

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1

We consider the problem of sorting $n$ elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (…