Question

Let A be an array of n numbers. Recall that a pair of indices i, j is said to be under an inversion if A[i] > A[j] and i < j. Design a divide-and-conquer based algorithm to count the number of inversions in an array of n numbers. You can start by splitting into two subproblems. Answer clearly how you do the merge step, then obtain a recurrence relation that captures the run time of the algorithm. Solve the recurrence relation. Write the complete pseudocode.

Answer 1

Check the explanation

Step-by-step explanation:

#include <stdio.h>

int inversions(int a[], int low, int high)

{

int mid= (high+low)/2;

if(low>=high)return 0 ;

else

{

int l= inversions(a,low,mid);

int r=inversions(a,mid+1,high);

int total= 0 ;

for(int i = low;i<=mid;i++)

{

for(int j=mid+1;j<=high;j++)

if(a[i]>a[j])total++;

}

return total+ l+r ;

}

}

int main() {

int a[]={5,4,3,2,1};

printf("%d",inversions(a,0,4));

return 0;

}

Check the output in the below attached image.