An Optimal Sorting Algorithm for Persistent Random Comparison Faults

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 (small) probability p, and comparing the same pair of elements multiple times always yields the same result. Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, i.e., the difference between its position in the sequence and its true rank. In this paper, we present the first O(nlog n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability when p<frac14. This settles the time complexity sorting with persistent comparison errors in the given range of p and shows that comparison errors do not increase its computational difficulty. Indeed, Omega(nlog n) time is necessary to archive a maximum dislocation of O(log n) even without comparison errors. Moreover, we prove that no algorithm can guarantee a maximum dislocation of o(log n) with high probability, nor a total dislocation of o(n) in expectation. To develop our sorting algorithm, we solve two related sub-problems, which might be of independent interest. More precisely, we show that O(log n) time suffices to find a position in which to insert a new element x in an almost-sorted sequence S of n elements having dislocation at most d=Omega(log n), so that the dislocation of x in the resulting sequence is O(d) with high probability (which can be equivalently thought as the problem of estimating the rank of x in S). We also show that the maximum (resp. total) dislocation of an approximately sorted sequence S of n elements can be lowered to O(log n) (resp. O(n)) in O(nd) time, w.h.p., where d is an upper bound on the maximum dislocation of S.