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

An array has $n$ different elements $[A_1, A_2, \ldots, 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}, \ldots, A_{i_n}]$ (It could be wrong)

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

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

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

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

My idea is as follows:

  1. When $m=n$, $E[S] = n$, surely
  2. When $m=n-1$, $E[S] = n-1+P(A_n \text{ in } A_{i_n})$

I dont know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.

  • 1
    $\begingroup$ Try to work out $m=1$ and selection sort, which is asking for the probability that the smallest element ends up first. $\endgroup$
    – Louis
    Apr 26, 2015 at 14:50
  • 1
    $\begingroup$ Related question. $\endgroup$
    – Raphael
    Apr 28, 2015 at 17:09
  • $\begingroup$ I'd imagine the answer might depend upon which sorting algorithm you are using (no?), so in questions 1 and 2 you should probably tell us which sorting algorithm you're asking about. Also, do you mean that if we use the comparator $k$ times, then all $k$ events are independent? For instance, if I use the comparator to compare $A_1$ to $A_2$, and then I compare those same two elements again, are the two results independent? $\endgroup$
    – D.W.
    May 2, 2015 at 1:37

1 Answer 1


The question seems ill-defined. A faulty/probabilistic comparator will have a radically different impact on different sort algorithms. Each algorithm will have a different, and potentially very complex, analysis.

One possibly interesting note is that you will get exactly reverse sort order when p=0. When p=0.5 the result will be unbiased on ascending vs descending, but the resulting permutations will not be equally likely.

  • $\begingroup$ Welcome to CS Stack Exchange! This seems to be more of a comment than an answer (when you have a little more reputation, you'll be able to post comments) but I agree that the question is ill-defined. As a new user, it's probably best to give your attention to well-defined questions so you can pick up enough reputation from upvotes to leave comments. $\endgroup$ Aug 18, 2015 at 10:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.