Sorting in a probabilistic order

Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.

One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0

• Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.

• Insert 3 into positions 1,2,3 with probabilities

$\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.

• Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the Plackett–Luce model from 1959. There are other models, for example Tallis–Dansie.

StackExchange Computer Science Q#73795, answer score: 5