Coping with erroneous information while sorting

The authors study the problem of sorting n distinct elements in ascending sequence according to a total order, using comparison queries which receive `yes´ or `no´ answers, but of which as many as e may be erroneous. In a half-lie version, all `yes´ answers are guaranteed to be correct and the errors are confined to `no´ answers. It is shown that the comparison query complexity of the sorting problem for this case is Ω(n log n+e), and an asymptotically optimal algorithm is demonstrated. In a full-lie version, both `yes´ and `no´ answers can be false. It is shown that the comparison query complexity of the sorting problem for this case is Ω(n log n+en)