5.9k views
If I have two lists of length 2 then no of comparisons in the worst case would be 2 only , since If I have say 10,20 in list A and 5,7 in list B so then on merging 10 is compared with 5 then 20 is compared with 7 so finally in 2 comparisons I have merged both the lists , so then how to calculate the average no of comparisons here ?
| 5.9k views

First of all, worst case would be 3 comparisons. For example, A = [10,20], B = [15,30]. Here number of comparisons would be 3.

Now for expected number of comparisons, suppose we are given two lists A = [x1,x2], B = [x3,x4]. For simplicity, suppose all 4 elements are distinct.

If we were to write all possible results of merging x1,x2,x3,x4, we have following $\binom{4}{2}=6$ possibilities (Note that in each possibility, x1 has to come before x2, and x3 before x4 because A and B are sorted)

x1,x2,x3,x4
x1,x3,x2,x4
x1,x3,x4,x2
x3,x4,x1,x2
x3,x1,x4,x2
x3,x1,x2,x4

Now we can have either 2 comparisons or 3 comparisons. We have 2 comparisons if either both x1,x2 < x3 or both x3,x4<x1, so P(2 comparisons) = 2/6

We will have 3 comparisons in rest of the 4 cases (you can verify), so P(3 comparisons) = 4/6

So $\text{E[num comparisons]} = 2*\text{P(2 comparisons)} + 3*\text{P(3 comparisons)}$

$= 2*\frac{2}{6} + 3*\frac{4}{6} = \frac{16}{6} = \frac{8}{3}$

We can generalize it for two lists $A$ and $B$ of size $m$. Number of ways in which final merged list $C$ can be formed is $\binom{2m}{m}$, because we have total $2m$ locations in $C$, out of which we can choose any $m$ locations to put elements of $A$, rest are filled by $B$.

Now we count number of comparisons done during merging. Suppose during merging, $A$ finishes first (other case is symmetrical, and we will multiply the count by 2). So number of comparisons will be size of list $C$ when $A$ finishes. So we argue on size of $C$ (let we call it $S$ when $A$ finishes).
Minimum value of $S$ is $m$ because when $A$ finishes, $C$ must contain at least $m$ elements, and maximum value of $S$ is $2m-1$, which happens when $B$ is left with just 1 element when $A$ finishes. So we make cases on $S$ :

$S = m$ : Only 1 case, when all elements of $A$ are smaller than of B.
$S = m+1$ : $C$ contains $m+1$ elements, out of which $m$ are of A, $1$ is of B, that 1 element of $B$ can take any location out of $m$ locations in C, so $\binom{m}{1}$ choices.
$S = m+2$ : $C$ contains $m+2$ elements, out of which $m$ are of A, $2$ are of B, those $2$ elements of $B$ can take any location out of $m+1$ locations in C, so $\binom{m+1}{2}$ choices.

This can go on till $S=2m-1$ : $\binom{2m-2}{m-1}$ choices.

So total number of comparisons in all cases
$=2*\left(m*1 + (m+1)*\binom{m}{1} + \ldots + (2m-1)*\binom{2m-2}{m-1}\right)$
Multiplication by $2$ outside is due to symmetry.

Finally, expected value of number of comparisons
$=\frac{2*\left(m*1 + (m+1)*\binom{m}{1} + \ldots + (2m-1)*\binom{2m-2}{m-1}\right)}{\binom{2m}{m}}$

We can generalize it similarly for different size lists.

selected by
0
Thank you sir for the generalization. :)
0
Why is maximum value of S is 2m-1 , it should be 2m+1 since B contains one extra element
+1
when S contains m+1 elements, the no ways in which 1 element of B can occupy the list C should be

m+1C1, why it is mc1??

can someone tell??
+1 vote

In Merge Procedure we generally have infinity() at the end of the array we like to merge

Here largest element of one array is smallest than the smallest element of another array

a = [10,20]

b = [5,7] In Example 1 the smallest array(ie a) smallest element is greater than the largest element of array b.Here number of comparsion is 5

In Example 2 the smallest array (ie b) the largest element is smaller than the smallest of array b.Here number of comparison is 3.

Thus it depends on array that how many comparison their will be.But the mandatory condition that (the smallest element of one array is larger than the largest of another) is to be fulfilled.

In your case the number of comparison is 2(as it fulfills the mandatory condition).

NOTE

*The infinity is put at the end of both the array because in (above discussed) array the element to compare with will be over at certain time, then  plays a immense role.

edited
0
How will you merge unsorted lists in O(a) or O(b) time?
0

Yes it is to be sorted.I have corrected that.Thanks

0
can u please explain how sentinel reduce the comparisions?