What type of algorithm is shown below 1 Set count00ileftjmid

What type of algorithm is shown below?

1) Set count=0,0,i=left,j=mid. C is the sorted list.
2) Traverse list1 and list2 until mid element or right element is encountered .
3) Compare list1[i] and list[j].
i) If list1[i]<=list2[j]
c[k++]=list1[i++]
else
c[k++]=list2[j++]
count = count + mid-i;
4) add rest elements of list1 and list2 in c.
5) copy sorted list c back to original list.
6) return count.

Solution

Answer :

Divide and conquer based algorithm

Explanation :

1.It is Divide and conquer based algorithm.It is Implemented using Merge sort.

2.The key concept is 2 count the number of inversion in merge procedure.

3.If an element of list 2 >element of list 1 than all the remaining element of list 1 are greater than this element.so,count=count+mid - i;

4.Recursively sort the list and find the no.of inversion.