Optimal Sorting with Persistent Comparison Errors

Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Omega(log n) and Omega(n), respectively, regardless of its running time.
We present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability.
This settles the time complexity of this problem and shows that comparison errors do not make the problem computationally more difficult: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds.