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.
Sorting in a probabilistic order
sorting;probability theory
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 < \phi \leq 1$:Start with the permutation 1.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 PlackettLuce model from 1959. There are other models, for example TallisDansie.