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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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