Sorting by Swaps with Noisy Comparisons

Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler

We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability $p<1/2$. We use this process as prototype for the behaviour o…