On sorting in the presence of erroneous information (Q1199884)

\textit{K. B. Lakshmanan}, \textit{B. Ravikumar} and \textit{K. Ganesan} [(*) Coping with erroneous information while sorting, IEEE Trans. Comput. 40(9), 1081-1084 (1991)] studied the following problem of sorting a given set \(X=\{x_ 1,x_ 2,\dots,x_ n\}\) of \(n\) distinct elements using binary comparisons of the form ``Is \(x_ i<x_ j\)?'', with two possible outcomes, ``yes'' and ``no'' for each comparison. However, some of the responses received for the comparisons could be erroneous. It is assumed that the number of errors can be at most \(e\), and \(e\) is known ahead of time. The authors established that if there are at most \(e\) erroneous responses, then the worst-case complexity of the sorting problem is \(\Omega(n\log n+en)\). They also presented an algorithm for the problem which requires at most \(O(n\log n+en+e^ 2)\) comparison queries. Clearly the algorithm is not optimal if \(e\) is large. We present an algorithm that uses at most \(O(n\log n+en)\) comparison queries, i.e. it matches the lower bound established in (*) for all values of \(e\).