  We study maximum selection and sorting of $n$ numbers using pairwise
comparators that output the larger of their two inputs if the inputs are more
than a given threshold apart, and output an adversarially-chosen input
otherwise. We consider two adversarial models. A non-adaptive adversary that
decides on the outcomes in advance based solely on the inputs, and an adaptive
adversary that can decide on the outcome of each query depending on previous
queries and outcomes.
  Against the non-adaptive adversary, we derive a maximum-selection algorithm
that uses at most $2n$ comparisons in expectation, and a sorting algorithm that
uses at most $2n \ln n$ comparisons in expectation. These numbers are within
small constant factors from the best possible. Against the adaptive adversary,
we propose a maximum-selection algorithm that uses $\Theta(n\log
(1/{\epsilon}))$ comparisons to output a correct answer with probability at
least $1-\epsilon$. The existence of this algorithm affirmatively resolves an
open problem of Ajtai, Feldman, Hassadim, and Nelson.
  Our study was motivated by a density-estimation problem where, given samples
from an unknown underlying distribution, we would like to find a distribution
in a known class of $n$ candidate distributions that is close to underlying
distribution in $\ell_1$ distance. Scheffe's algorithm outputs a distribution
at an $\ell_1$ distance at most 9 times the minimum and runs in time
$\Theta(n^2\log n)$. Using maximum selection, we propose an algorithm with the
same approximation guarantee but run time of $\Theta(n\log n)$.
