<p>I believe this takes <span class="math-container">$\Theta(n^2)$</span> oracle calls without replacement, and <span class="math-container">$\Theta(n^2\log n)$</span> oracle calls with replacement.</p>
<p><strong>Lower bound</strong>: Assume my list has a single pair <span class="math-container">$x[i], x[i+1]$</span> out of order.  Then I can sort if and only if <span class="math-container">$(i,i+1)$</span> is chosen as a pair.  That means we require <span class="math-container">$\Omega(n^2)$</span> iterations in expectation without replacement (simple proof: there's a <span class="math-container">$1/2$</span> probability that <span class="math-container">$(i,i+1)$</span> is in the last <span class="math-container">$\binom{n}{2}/2$</span> pairs we pick) , and <span class="math-container">$\Omega(n^2\log n)$</span> iterations with replacement (by classic coupon collector).</p>
<p><strong>Upper bound</strong>: The conversation in the comments seems to indicate two versions of the problem.  I'll discuss the differences; then solve each below.</p>
<p>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).</p>
<p>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 <span class="math-container">$x[i]$</span> and <span class="math-container">$x[j]$</span>, I must immediately act on that information, and can't store it for later.  In fact, one may even limit to the following algorithm:</p>
<p>For <span class="math-container">$T$</span> time steps:</p>
<ol>
<li>ask the oracle for a random <span class="math-container">$(i,j)$</span></li>
<li>If <span class="math-container">$i &lt; j$</span> but <span class="math-container">$x[i] &gt; x[j]$</span>, then swap <span class="math-container">$x[i]$</span> and <span class="math-container">$x[j]$</span></li>
</ol>
<p>This limited case is more difficult, but even for this most restricted algorithm, after <span class="math-container">$T = O(n^2\log n)$</span> 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 &quot;unsort&quot; a previously-seen pair this algorithm will never sort it).</p>
<p><strong>The first (simpler) case:</strong> After <span class="math-container">$O(n^2)$</span> iterations without replacement, or <span class="math-container">$O(n^2\log n)$</span> 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.</p>
<p><strong>The second case:</strong> Each time we swap reduces the number of inversions by at least 1.  (Consider a swap of <span class="math-container">$x[i]$</span> and <span class="math-container">$x[j]$</span> where <span class="math-container">$x[i] &lt; x[j]$</span>, but <span class="math-container">$j &lt; i$</span>; swapping <span class="math-container">$j$</span> and <span class="math-container">$i$</span> reduces the number of inversions by 1.  Any element <span class="math-container">$x[a]$</span> (with <span class="math-container">$a\neq i,j$</span>) which has its number of inversions changed must have <span class="math-container">$j &lt; a &lt; i$</span>.  Consider 3 cases for the ordering of <span class="math-container">$x[a]$</span> vs <span class="math-container">$x[i]$</span> and <span class="math-container">$x[j]$</span>.  If <span class="math-container">$x[a] &lt; x[i] &lt; x[j]$</span>, or <span class="math-container">$x[i] &lt; x[j] &lt; x[a]$</span>, the number of inversions <span class="math-container">$a$</span> is involved with stays the same.  If <span class="math-container">$x[i] &lt; x[a] &lt; x[j]$</span>, the number of inversions <span class="math-container">$a$</span> is involved with decreases by <span class="math-container">$2$</span>).</p>
<p>If the current number of inversions is <span class="math-container">$p\binom{n}{2}$</span>, then the probability of choosing a currently-inverted pair--and therefore decreasing the number of inversions--is <span class="math-container">$p$</span>.  So, after <span class="math-container">$1/p$</span> iterations, I'm expected to see the number of inversions decrease.  Let <span class="math-container">$X_i$</span> be the number of iterations until the number of inversions drops to <span class="math-container">$&lt; i$</span> from <span class="math-container">$i$</span> (we'll let <span class="math-container">$X_i = 0$</span> if we never have <span class="math-container">$i$</span> inversions), and let <span class="math-container">$X$</span> be the total number of iterations done by the algorithm.  Then <span class="math-container">$X = \sum X_i$</span>.  Furthermore, <span class="math-container">$\text{E}[X_i] \leq \binom{n}{2}/i$</span>.  So using linearity of expectation:</p>
<p><span class="math-container">$$
\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)
$$</span></p>
<p>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 <span class="math-container">$T = O(n^2\log n)$</span> iterations is sufficient with high probability as well.</p>
<p>Incidentally, this seems like an excellent homework problem for students who have just learned the coupon collector analysis.</p>

CC BY-SA 4.0
2022-10-03T18:07:08.830Z
2022-10-09T00:48:23.090Z
2022-10-09T00:48:23.090Z
SamM
<p>Not a complete answer, but here's a start.
Consider the index <span class="math-container">$p_{k} \in \{1,\dots n \}$</span> to represent the <span class="math-container">$k$</span>th object in the series, with respect to order. We have:
<span class="math-container">$$x[p_{k}] &lt; x[p_{j}] \Leftrightarrow k &lt; j $$</span></p>
<p>Which pairs <span class="math-container">$(p_{i},p_{j})$</span> do we need to get from the oracle in order to deduce the relationships between all other pairs? If we get for example that <span class="math-container">$x[i]&gt; x[j]$</span> and <span class="math-container">$x[j]&gt; x[k]$</span>, then we can deduce <span class="math-container">$x[i]&gt;x[k]$</span> from the transitivity of order relation. But there are exactly <span class="math-container">$(n-1)$</span> pairs that can not be deduced from others by transitivity: pairs of the form <span class="math-container">$(p_{k},p_{k+1})$</span>, where <span class="math-container">$k\in \{1,n-1\}$</span>. Ie. pairs of consecutive elements.</p>
<p>So, given an initial (unknown) ordering of our elements:
<span class="math-container">$$x[p_{1}], x[p_{2}] \dots x[p_{n}] $$</span>
we need to ask the oracle until for every <span class="math-container">$k\in \{1,n-1\}$</span>, at least one element of the set <span class="math-container">$\{(p_{k},p_{k+1}), (p_{k+1},p_{k})\}$</span>  has been picked. To simulate the probability efficiently, we can drop the <span class="math-container">$p$</span> and just use the index <span class="math-container">$k$</span> to refer to <span class="math-container">$p_{k}$</span>.
Of the set: <span class="math-container">$$\{(a,b)|\; a,b\in\{1,n\}, a\neq b  \}$$</span> we select elements with or without replacement until for every <span class="math-container">$k\in \{1,n-1\}$</span>, at least one element of the set <span class="math-container">$\{(k,k+1), (k+1,k)\}$</span> has been picked. The average number of selections is the average number of queries required for the oracle to sort a set of size <span class="math-container">$n$</span>.</p>
<hr />
<p>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 <span class="math-container">$n^2$</span>. Here is the average number of needed comparisons without replacement for <span class="math-container">$n=\{10,20,30,40,50,60\}$</span>:
<span class="math-container">$$\{65.1766, 305.025, 729.482, 1341.58, 2143.04, 3135.02\}$$</span></p>
<p>A better approximation for the average number of comparisons without replacement would be <span class="math-container">$n^{1.96622}$</span>. Recurrence formulas can be used to compute the average number of comparisons with replacement, which give for <span class="math-container">$n=\{10,20,30,40,50,60\}$</span> the following numbers:</p>
<p><span class="math-container">$$\{127.304, 674.071, 1723.32, 3317.76, 5487.03, 8253.87\}$$</span></p>
<p>A good estimator would be <span class="math-container">$n^{2.20266}$</span> . So the average number of required comparisons from the oracle without replacement goes a bit below <span class="math-container">$O(n^2)$</span>, the number with replacement goes a bit above it.</p>

CC BY-SA 4.0
2022-10-03T15:27:13.790Z
2022-10-03T16:56:12.813Z
2022-10-03T16:56:12.813Z
user3257842
<p>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 <a href="https://gist.github.com/murbard/5c711d8efe114c1ecb2152579937064c" rel="nofollow noreferrer">OP's Python gist</a>: 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.</p>
<p><strong>Lemma 1.</strong> <em>(i) <strong>With replacement</strong> the expected number of comparisons is <span class="math-container">$${n \choose 2} H_{n-1},$$</span> where <span class="math-container">$H_k = \sum_{i=1}^k \frac 1 i \approx 0.5+\ln k$</span> is the <span class="math-container">$k$</span>th harmonic number.</em></p>
<p><em>(ii) <strong>Without replacement</strong>, the expected number of comparisons is</em> <span class="math-container">$$n^2/2 - n + 3/2 - 1/n.$$</span></p>
<p><em>Proof.</em> Assume WLOG that the set of numbers in <span class="math-container">$x$</span> is <span class="math-container">$[n]$</span>.  Let random variable <span class="math-container">$T$</span> be the total number of steps.</p>
<p>As observed in @user3257842's answer, a necessary and sufficient condition for the full order to be known is that, for all <span class="math-container">$i\in [n-1]$</span>, the positions holding elements <span class="math-container">$i$</span> and <span class="math-container">$i+1$</span> have been compared.  Call such positions &quot;neighbors&quot;.</p>
<p><em>Proof of Part (i).</em> For <span class="math-container">$m \in [n-1]$</span>, let random variable <span class="math-container">$T_m$</span> be the number of steps such that, at the start of the step, the number of neighbors that have not yet been compared is <span class="math-container">$m$</span>.  Then the total number of steps is <span class="math-container">$T=T_{n-1} + T_{n-2} + \cdots + T_1$</span>.  By linearity of expectation, <span class="math-container">$E[T] = \sum_{m=1}^{n-1} E[T_m]$</span>.  To finish, we calculate <span class="math-container">$E[T_m]$</span> for any <span class="math-container">$m\in [n-1]$</span>.</p>
<p>Consider any <span class="math-container">$m\in [n-1]$</span>.  Consider any iteration that starts with <span class="math-container">$m$</span> neighbors not yet compared.  Given this, <span class="math-container">$m$</span> of the <span class="math-container">$n\choose 2$</span> 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 <span class="math-container">$m/{n\choose 2}$</span>, reduces by 1.  It follows that <span class="math-container">$E[T_m]$</span>, the expected number of steps that start with <span class="math-container">$m$</span> uncompared neighbors, is <span class="math-container">${n\choose 2}/m$</span>.</p>
<p>So <span class="math-container">$E[T] = \sum_{m=1}^{n-1} {n\choose 2}/m = {n\choose 2} H_{n-1}$</span>, proving Part (i).</p>
<p><em>Proof of Part (ii).</em> View the process as follows: a random permutation of the <span class="math-container">$n\choose 2$</span> pairs is chosen, and then the algorithm checks each pair (in the chosen order) just until it has compared all neighboring pairs.</p>
<p>That is, we want the expected position of the last neighboring pair in the random ordering of pairs.  There are <span class="math-container">$n-1$</span> neighboring pairs and <span class="math-container">${n\choose 2} - (n-1) = {n-1\choose 2}$</span> non-neighboring pairs.  By a standard calculation, the expected position of the last neighboring pair is <span class="math-container">${n \choose 2} - {n-1\choose 2}/n = n^2/2 - n + 3/2 - 1/n$</span>. <span class="math-container">$~~~\Box$</span></p>
<p>Here is some intuition about the last &quot;standard calculation&quot;.  Suppose you choose a <span class="math-container">$k$</span>-subset <span class="math-container">$S$</span> uniformly at random from <span class="math-container">$[m+k]$</span>.  What's the expectation of <span class="math-container">$\max S$</span>?  The <span class="math-container">$k$</span> chosen elements divide the <span class="math-container">$m$</span> unchosen elements into <span class="math-container">$k+1$</span> intervals of total size <span class="math-container">$m$</span>.  By a symmetry argument the expected number of elements in each of these intervals is the same, so each interval has size <span class="math-container">$m/(k+1)$</span> in expectation.  In particular, the expected size of the last interval is <span class="math-container">$m/(k+1)$</span>, so the expectation of the largest element is <span class="math-container">$m+k - m/(k+1)$</span>.</p>
<p>In our case <span class="math-container">$m+k = {n \choose 2}$</span> and <span class="math-container">$k=n-1$</span>.</p>

CC BY-SA 4.0
2022-10-03T18:22:49.960Z
2022-10-04T20:14:05.103Z
2022-10-04T20:14:05.103Z
Neal Young
<p>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] &lt; x[j] and (j, i) if x[i] &gt; x[j].</p>
<p>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.</p>

CC BY-SA 4.0
2022-10-03T15:10:38.893Z
maybe writting a small simulation program (Monte Carlo Simulation) that generates a random array and calls this oracle, while testing for full sorting after each call, can give you a rough estimation...
Avi Tal
CC BY-SA 4.0
2022-10-03T15:12:46.963Z
After the oracle has picked the pair $(i , j)$, can it in the future pick the pair $(j,i)$, or does no replacement rule apply here? We have $i != j$ , but not $i < j$, which would prevent duplicates.
user3257842
CC BY-SA 4.0
2022-10-03T15:25:56.900Z
@AviTal sure https://gist.github.com/murbard/5c711d8efe114c1ecb2152579937064c

It's slow though
Arthur B
CC BY-SA 4.0
2022-10-03T15:26:02.583Z
@user3257842 interested in the answer with and without replacement
Arthur B
CC BY-SA 4.0
2022-10-03T15:49:46.367Z
@NealYoung you can assume that the prior on the order of the list is uniform over the set of all permutations.
Arthur B
CC BY-SA 4.0
2022-10-03T15:51:09.660Z
I assumed the list is unordered. To deduce the (unknown) correct order, the oracle needs to give you comparisons between every pair of consecutive elements of the order-to-be-deduced (consecutive with respect to the order).  Then you can use those reconstruct the order (ie. sort the list).
user3257842
CC BY-SA 4.0
2022-10-03T16:09:15.887Z
@NealYoung it takes at least $n \log n$ comparisons on average to sort, so the coupon collection argument would look more like $n \log^2 n$ but that's handwavy. Upper bound seems credible.
Arthur B
CC BY-SA 4.0
2022-10-03T16:44:31.770Z
You get the n² log n upper bound merely by invoking coupon collection on all pairs, no need to count inversions. When I speak of no replacement, I mean that every pair is returned at most once by the oracle, putting a O(n²) upper bound.
Arthur B
CC BY-SA 4.0
2022-10-03T17:22:21.187Z
I've deleted my comments above, which were based on a misunderstanding of the question.  (I assumed that you had in mind the following process: *choose a random pair x[i], x[j]; swap them if they are out of order; repeat*; and that you wanted to know the expected number of steps until the list was sorted (with replacement it is $\Omega(n^2)$ and $O(n^2\log n)$, but, per your Python gist, this is not the problem you care about.)  Maybe edit the post to clarify the problem?
Neal Young
<randomness><sorting>
Expected number of random comparisons needed to sort a list
Arthur B
# Expected number of random comparisons needed to sort a list

(Asked by: username_0 on 2022-10-03)

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.

**Tags:** randomness, sorting

> **Comments:**
> **username_1**: maybe writting a small simulation program (Monte Carlo Simulation) that generates a random array and calls this oracle, while testing for full sorting after each call, can give you a rough estimation...  
> **username_2**: After the oracle has picked the pair $(i , j)$, can it in the future pick the pair $(j,i)$, or does no replacement rule apply here? We have $i != j$ , but not $i < j$, which would prevent duplicates.  
> **username_0**: @AviTal sure https://gist.github.com/murbard/5c711d8efe114c1ecb2152579937064c  It's slow though  
> **username_0**: @username_2 interested in the answer with and without replacement  
> **username_0**: @NealYoung you can assume that the prior on the order of the list is uniform over the set of all permutations.  
> **username_2**: I assumed the list is unordered. To deduce the (unknown) correct order, the oracle needs to give you comparisons between every pair of consecutive elements of the order-to-be-deduced (consecutive with respect to the order).  Then you can use those reconstruct the order (ie. sort the list).  
> **username_0**: @NealYoung it takes at least $n \log n$ comparisons on average to sort, so the coupon collection argument would look more like $n \log^2 n$ but that's handwavy. Upper bound seems credible.  
> **username_0**: You get the n² log n upper bound merely by invoking coupon collection on all pairs, no need to count inversions. When I speak of no replacement, I mean that every pair is returned at most once by the oracle, putting a O(n²) upper bound.  
> **username_3**: I've deleted my comments above, which were based on a misunderstanding of the question.  (I assumed that you had in mind the following process: *choose a random pair x[i], x[j]; swap them if they are out of order; repeat*; and that you wanted to know the expected number of steps until the list was sorted (with replacement it is $\Omega(n^2)$ and $O(n^2\log n)$, but, per your Python gist, this is not the problem you care about.)  Maybe edit the post to clarify the problem?  

---

## 3 answers

### Answer by username_3 on 2022-10-03. Score: 12 | Accepted answer

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](https://gist.github.com/murbard/5c711d8efe114c1ecb2152579937064c): 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 @username_2'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$.


---

### Answer by username_4 on 2022-10-03. Score: 9

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:

1. ask the oracle for a random $(i,j)$
2. If $i < j$ but $x[i] > x[j]$, then swap $x[i]$ and $x[j]$

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.


---

### Answer by username_2 on 2022-10-03. Score: 6

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.


---

