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
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?