  We study very simple sorting algorithms based on a probabilistic comparator
model. In our model, errors in comparing two elements are due to (1) the energy
or effort put in the comparison and (2) the difference between the compared
elements. Such algorithms keep comparing pairs of randomly chosen elements, and
they correspond to Markovian processes. The study of these Markov chains
reveals an interesting phenomenon. Namely, in several cases, the algorithm
which repeatedly compares only adjacent elements is better than the one making
arbitrary comparisons: on the long-run, the former algorithm produces sequences
that are "better sorted". The analysis of the underlying Markov chain poses new
interesting questions as the latter algorithm yields a non-reversible chain and
therefore its stationary distribution seems difficult to calculate explicitly.
