Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator? Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's prominent failure to write a uniform permutation generator, my question is thus:

Is there a comparison based sorting algorithm which will, depending on our implementation of the comparator:


return the elements in sorted order when using a true comparator (that is, the comparison does what we expect in a standard sorting algorithm) 
return a uniformly random permutation of the elements when the comparator is replaced by a fair coin flip (that is, return x &lt; y = true with probability 1/2, regardless of the value of x and y)


The code for the sorting algorithm must be the same. It is only the code inside the comparison "black box" which is allowed to change.
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$.