**Problem:**Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

**Solution:**

unsigned long countSplitInversions(int *arr, unsigned long mid, unsigned long len)

{

vector<int> tempVect(arr, arr + mid);

unsigned long count = 0;

unsigned long i = 0, j = mid, k = 0;

for(; i < mid && j < len;)

{

if(arr[j] < tempVect[i])

{

arr[k++] = arr[j++];

count += (mid - i);

}

else

{

arr[k++] = tempVect[i++];

}

}

if(j < len)

{

while(j < len)

arr[k++] = arr[j++];

}

else if(i < mid)

{

while(i < mid)

arr[k++] = tempVect[i++];

}

return count;

}

unsigned long countInversions(int *arr, unsigned long len)

{

if(len == 1)

return 0;

unsigned long mid = len/2;

unsigned long leftInversions = countInversions(arr, mid);

unsigned long rightInversions = countInversions(arr + mid, len - mid);

unsigned long splitInversions = countSplitInversions(arr, mid, len);

return leftInversions + rightInversions + splitInversions;

}

## No comments:

## Post a Comment