298 views
Let us a consider a series of events where a random partition procedure always picks the median element among n distinct numbers dividing the array into two equal halves ( ignore floor and ceiling). What is the probability that such a partition procedure always picks the median element in all subsequent arrays till the entire array is sorted.
| 298 views

The probability of selecting the median among n numbers is  1/n

The probability of selecting the median from the 2 n/2 partitions is (2/n)*(2/n) = 22/n2

In a similar way the series will appear as  (1/n) x (22/n2) x (44/n)x....x (Log nlog n/nlog n-1)

### So the probability of picking median till the entire array is sorted will be    $\frac{\prod_{i=0}^{log n} (2^{i})^{2^{i}}}{(n^{2})^{\frac{(Log n-1)Log n}{2}}}$

by Active (2.6k points)