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

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 > 2$, there is no way to write $1/n!$ in the form $A/2^B$.

StackExchange Computer Science Q#10656, answer score: 4