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.