# How can I calculate the exact expected value of merge sort comparison (not O(n))?

First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list)

Second, I'm trying to solve the exact value of expected value of merge sort in each comparison. As you might know that each comparison cost $O(n)$, but it turn out that some this case I will have to consider that it might less than $n$.

For example, I have first list as U and I may split it as below. $$U = \left\{8,3,1,6,15,4,7,10,9,2\right\}$$ $$A = \left\{3,1,8,4,2\right\}$$ $$B = \left\{6,15,7,10,9\right\}$$

Then, we might sort at some point to get A and B as below. $$A = \left\{1,2,3,4,8\right\}$$ $$B = \left\{6,7,9,10,15\right\}$$ Which it turn out that we don't need to make any comparisons for 9,10,15.

That makes this would have only 7 comparisons instead of 10 times.

I did try to think about recurrence but it turn out that might have loads in calculation. Therefore, I try to compute by using something like $$E[X] = \sum_{i=1}^{n}(n-t)(Pr\left\{X_A>Value(t)\right\}+Pr\left\{X_B>Value(t)\right\})$$ $$Value(t) = Min(Max(A),Max(B))$$ This is the furthest point can come. Can you give me any advises to go further?

## 1 Answer

Suppose the initial list $U$ is some permutation of $[1,2,\ldots,n]$. In merging the two sorted sub-lists, $j$ will be compared to $k$ (with $j < k$) iff $k$ is the first number $> j$ in the opposite sub-list to $j$. Thus the probability that $j$ will be compared to $k$ is $2^{-(k-j)}$. Add these up for all ordered pairs $(j,k)$ with $j < k$ and you get the expected number of comparisons.