Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator?
No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n &gt; 2$, there is no way to write $1/n!$ in the form $A/2^B$.