# Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $$n$$ items $$x_1, \ldots, x_n$$. Until you can sort the list, you are given one of the $${n \choose 2}$$ possible binary comparisons uniformly at random (with replacement).

On average, how many of these random comparisons will you need to be able to sort the list?

Some follow-up questions:

1. What does the distribution for the number of comparisons needed look like?
2. What is the answer if you use $$k$$-ary comparisons instead of binary ones.
3. What is the answer if the comparisons are made without replacement (i.e. you won't get the same comparison twice)?
4. Given a set of comparisons, how can one check if the list is sort-able? I'm almost certain the answer is to construct a DAG and topological sort, but I just want to confirm.

An exact-ish answer would be nice, but a big $$O$$ answer is fine too, I suppose.

• FYI, the usual rule is one question per post.
– D.W.
Dec 15, 2019 at 7:58

Asympotically, you'll need $$\Theta(n^2 \log n)$$ comparisons.
Suppose $$x_{(1)},\dots,x_{(n)}$$ denotes the elements in sorted order. Then if you don't see a comparison between $$x_{(1)}$$ and $$x_{(2)}$$, you will have no way to tell which order they should appear in. The same is true of every pair of adjacent element. So, there are $$n-1$$ coupons (one per adjacent pair of elements), and you need to collect them all. Based on the coupon collector problem, we know you'll need $$\Theta(n \log n)$$ randomly chosen coupons before we've collected them all. Each observation has a $$2/n$$ chance of being a coupon, so in total we'll need $$\Theta(n^2 \log n)$$ observations before we've collected all the coupons. If we collect all the coupons, we can sort the $$x$$'s; if we're missing any coupon, we can't sort them.
If comparisons are chosen without replacement, then you need $$\Theta(n^2)$$ observations.