Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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