Merge Sort

Question

The average no. of comparisons performed by the merge sort algorithm, in merging two sorted lists of length 2 is -

a) 8/3

b) 8/5

c) 11/7

d) 11/6

Comments

8/3 ??

---

how?

I am getting 2+2-1=3 comparison

Answer 1

Let's first solve this question with Brute-force approach.

Let $1,2,3,4$ be the four numbers.

So, We have Two sorted lists of $2,2$ item each. So, We have ⁴C₂ = 6  possibilities

$1,2$ and $3,4$  => $2$ comparisons required.

$3,4$ and $1,2$  => $2$ comparisons required.

$1,3$ and $2,4$ =>  $3$ comparisons required.

$2,4$ and $1,3$ =>  $3$ comparisons required.

$1,4$ and $2,3$ =>  $3$ comparisons required.

$2,3$ and $1,4$ =>  $3$ comparisons required.

So, Average number of Comparisons (Expected number of comparisons in a merge step ) = $16/6 = 8/3$

---

Now, that is Brute-force approach and clearly, it is efficient only for small cases like the one asked.

There is a General formula for Expected number of comparisons in a merge step When Each Sorted array has $n/2$ elements :

Expected number of comparisons in a merge step = $\frac{n^2}{n+2}$ ..Note that $n/2$ is the number of elements in both sorted arrays, Not $n$.

 The expected number of comparisons is pretty close to $n−2$.  As  $\frac{n^2}{n+2}$ $≈$ $n-2$

Comments

@Deepak bhai

Expected number of comparisons in a merge step = n²   / n+2 ???

Answer 2

consider 1,2,3,4 is required sorted order. then,

two list can be (i) 1, 2 and 3,4  (ii) 1, 3 and 2,4  (iii) 1, 4 and 2, 3

The number of comparisons needed in each case will be 2, 3, 3 respectively.

& So, average number of comparisons will be (2+3+3)/3= 8/3

Comments

@ srestha ma'am, correct me if i'm wrong!

---

What if two lists are

(i) 3,4 and 1,2  (ii) 2,4 and 1,3  (iii) 2,3 and 1,4

so avg number of comparisons for total cases - (2+3+3+2+3+3) /6 = 8/3

although answer will not change but this can be possibility. Right?

---

@  Shubhgupta yes!