# Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it.

An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ （random order）.

We have a comparator $C$, but it has a probability $p$ to return correct results.

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $[A_{i_1}, A_{i_2}, ..., A_{i_n}]$ (It could be wrong).

Now given a number $m$ ($m < n$), the question is as follows:

What is Expectation of size $S$ of Intersection between $\{A_1, A_2, ...， A_m\}$ and $\{A_{i_1}, A_{i_2}, ..., A_{i_n}\},$ in other words, what is $E[S]$?

Any relationship among $m$, $n$ and $p$ ?

If we use different sorting algorithm, how will $E[S]$ change ?

My idea is as follows:

When $m=n$, $E[S] = n$, surely. When $m=n-1$, $E[S] = n-1+P(A_n$ in $A_{i_n})$. I don't know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.

• Since [A1,...,An] are in random order, I think that E[S] does not depend on p, e.g. P(A1=Ai1) = 1/n. See my answer + comments here: stackoverflow.com/questions/29876160/… – coproc Apr 27 '15 at 9:24
• Side reading on that subject: Beyond Efficiency, CACM. – lhf May 20 '16 at 0:25