sorting with noisy but persistent answers
For constant $p&gt;0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.

In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, then $D = \Omega(\log |A|)$.  

The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $O(\log |A|)$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.

The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $O(\log |A|)$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $p$ needs to be smaller than some constant ($1/32$, $1/20$, or $1/16$):


Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.
Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.
Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.
Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.




1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).