Quicksort where element comparison outcome is random. Probability of element being in a certain position So we have this block of pseudocode:

Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];
qsort(Monsters,rand_compare);



  qsort() sorts the array via quicksort where we use the last element
  as pivot. To compare two elements it uses rand_compare, which, with
  equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or
  "2. element is bigger" and never "both are equal". What is the
  probability that M8 appears in position 0, 1 or 2, respectively, after
  applying qsort ?


I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?
In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625