Consider the task of sorting a list x of size n by repeatedly querying an oracle. The oracle draws, without replacement, a random pair of indices (i, j), with i != j, and returns (i, j) if x[i] < x[j] and (j, i) if x[i] > x[j].
How many times, on average, do we need to query the oracle to sort the list? How is that average affected if the draw is made with replacement? Looking for a formula but an asymptotic estimate or an order would also be great.
This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes one random comparison, and the process stops as soon as the comparisons made are sufficient to determine the total order.
Lemma 1. (i) With replacement the expected number of comparisons is $${n \choose 2} H_{n-1},$$ where $H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$ is the $k$th harmonic number.
(ii) Without replacement, the expected number of comparisons is $$n^2/2 - n + 3/2 - 1/n.$$
Proof. Assume WLOG that the set of numbers in $x$ is $[n]$. Let random variable $T$ be the total number of steps.
As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all $i\in [n-1]$, the positions holding elements $i$ and $i+1$ have been compared. Call such positions "neighbors".
Proof of Part (i). For $m \in [n-1]$, let random variable $T_m$ be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is $m$. Then the total number of steps is $T=T_{n-1} + T_{n-2} + \cdots + T_1$. By linearity of expectation, $E[T] = \sum_{m=1}^{n-1} E[T_m]$. To finish, we calculate $E[T_m]$ for any $m\in [n-1]$.
Consider any $m\in [n-1]$. Consider any iteration that starts with $m$ neighbors not yet compared. Given this, $m$ of the $n\choose 2$ possible comparisons would compare one not-yet compared pair of neighbors, while the remaining comparisons would not (so would leave the number of uncompared neighbors unchanged). So the number of not-yet-compared neighbors either stays the same, or, with probability $m/{n\choose 2}$, reduces by 1. It follows that $E[T_m]$, the expected number of steps that start with $m$ uncompared neighbors, is ${n\choose 2}/m$.
So $E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$, proving Part (i).
Proof of Part (ii). View the process as follows: a random permutation of the $n\choose 2$ pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.
That is, we want the expected position of the last neighboring pair in the random ordering of pairs. There are $n-1$ neighboring pairs and ${n\choose 2} - (n-1) = {n-1\choose 2}$ non-neighboring pairs. By a standard calculation, the expected position of the last neighboring pair is ${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$. $~~~\Box$
Here is some intuition about the last "standard calculation". Suppose you choose a $k$-subset $S$ uniformly at random from $[m+k]$. What's the expectation of $\max S$? The $k$ chosen elements divide the $m$ unchosen elements into $k+1$ intervals of total size $m$. By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size $m/(k+1)$ in expectation. In particular, the expected size of the last interval is $m/(k+1)$, so the expectation of the largest element is $m+k - m/(k+1)$.
In our case $m+k = {n \choose 2}$ and $k=n-1$.
I believe this takes $\Theta(n^2)$ oracle calls without replacement, and $\Theta(n^2\log n)$ oracle calls with replacement.
Lower bound: Assume my list has a single pair $x[i], x[i+1]$ out of order. Then I can sort if and only if $(i,i+1)$ is chosen as a pair. That means we require $\Omega(n^2)$ iterations in expectation without replacement (simple proof: there's a $1/2$ probability that $(i,i+1)$ is in the last $\binom{n}{2}/2$ pairs we pick) , and $\Omega(n^2\log n)$ iterations with replacement (by classic coupon collector).
Upper bound: The conversation in the comments seems to indicate two versions of the problem. I'll discuss the differences; then solve each below.
In the first, we just get a stream of comparisons; I just keep these comparisons in some data structure for later use (this case is easier as it reduces to the coupon collector's problem directly).
In the second case, you insist that the sorting must be in place, and I cannot keep any extra metadata: when the oracle gives me the order of $x[i]$ and $x[j]$, I must immediately act on that information, and can't store it for later. In fact, one may even limit to the following algorithm:
For $T$ time steps:
This limited case is more difficult, but even for this most restricted algorithm, after $T = O(n^2\log n)$ expected time steps we still sort--even without a black box reduction it essentially becomes a coupon collector problem. Note that I must insist on with replacement here, as otherwise the problem is impossible (if we "unsort" a previously-seen pair this algorithm will never sort it).
The first (simpler) case: After $O(n^2)$ iterations without replacement, or $O(n^2\log n)$ with replacement (via coupon collector), I have compared all pairs with high probability. I'll keep track of all previous comparisons in, say, a DAG, and then I can sort using whatever method I want.
The second case: Each time we swap reduces the number of inversions by at least 1. (Consider a swap of $x[i]$ and $x[j]$ where $x[i] < x[j]$, but $j < i$; swapping $j$ and $i$ reduces the number of inversions by 1. Any element $x[a]$ (with $a\neq i,j$) which has its number of inversions changed must have $j < a < i$. Consider 3 cases for the ordering of $x[a]$ vs $x[i]$ and $x[j]$. If $x[a] < x[i] < x[j]$, or $x[i] < x[j] < x[a]$, the number of inversions $a$ is involved with stays the same. If $x[i] < x[a] < x[j]$, the number of inversions $a$ is involved with decreases by $2$).
If the current number of inversions is $p\binom{n}{2}$, then the probability of choosing a currently-inverted pair--and therefore decreasing the number of inversions--is $p$. So, after $1/p$ iterations, I'm expected to see the number of inversions decrease. Let $X_i$ be the number of iterations until the number of inversions drops to $< i$ from $i$ (we'll let $X_i = 0$ if we never have $i$ inversions), and let $X$ be the total number of iterations done by the algorithm. Then $X = \sum X_i$. Furthermore, $\text{E}[X_i] \leq \binom{n}{2}/i$. So using linearity of expectation:
$$ \text{E}[X] \leq \sum_{i = 1}^{n^2} \text{E}[X_i] \leq \sum_{i=1}^{n^2} \binom{n}{2}/i = O(n^2\log n) $$
You may notice that this is almost exactly the classic coupon collector problem analysis. The difference here is that we don't always know which coupon we collect (we may even unfix previously-fixed pairs)---but the total number of pairs we invert keeps improving. I would imagine that we can show that $T = O(n^2\log n)$ iterations is sufficient with high probability as well.
Incidentally, this seems like an excellent homework problem for students who have just learned the coupon collector analysis.
Not a complete answer, but here's a start. Consider the index $p_{k} \in \{1,\dots n \}$ to represent the $k$th object in the series, with respect to order. We have: $$x[p_{k}] < x[p_{j}] \Leftrightarrow k < j $$
Which pairs $(p_{i},p_{j})$ do we need to get from the oracle in order to deduce the relationships between all other pairs? If we get for example that $x[i]> x[j]$ and $x[j]> x[k]$, then we can deduce $x[i]>x[k]$ from the transitivity of order relation. But there are exactly $(n-1)$ pairs that can not be deduced from others by transitivity: pairs of the form $(p_{k},p_{k+1})$, where $k\in \{1,n-1\}$. Ie. pairs of consecutive elements.
So, given an initial (unknown) ordering of our elements: $$x[p_{1}], x[p_{2}] \dots x[p_{n}] $$ we need to ask the oracle until for every $k\in \{1,n-1\}$, at least one element of the set $\{(p_{k},p_{k+1}), (p_{k+1},p_{k})\}$ has been picked. To simulate the probability efficiently, we can drop the $p$ and just use the index $k$ to refer to $p_{k}$. Of the set: $$\{(a,b)|\; a,b\in\{1,n\}, a\neq b \}$$ we select elements with or without replacement until for every $k\in \{1,n-1\}$, at least one element of the set $\{(k,k+1), (k+1,k)\}$ has been picked. The average number of selections is the average number of queries required for the oracle to sort a set of size $n$.
Edit: I've used the above to implement a recurrence formula for testing, and the number of comparisons needed from the oracle with replacement seems to tend towards $n^2$. Here is the average number of needed comparisons without replacement for $n=\{10,20,30,40,50,60\}$: $$\{65.1766, 305.025, 729.482, 1341.58, 2143.04, 3135.02\}$$
A better approximation for the average number of comparisons without replacement would be $n^{1.96622}$. Recurrence formulas can be used to compute the average number of comparisons with replacement, which give for $n=\{10,20,30,40,50,60\}$ the following numbers:
$$\{127.304, 674.071, 1723.32, 3317.76, 5487.03, 8253.87\}$$
A good estimator would be $n^{2.20266}$ . So the average number of required comparisons from the oracle without replacement goes a bit below $O(n^2)$, the number with replacement goes a bit above it.
