Reverse Pairs

/* 
  You are given an array/list say ‘ARR’ of size ‘N’. We call pair (i, j) a Reverse Pair when i < j and 'ARR[i]' > 2 * 'ARR[j]'.
  Your task is to find the number of Reverse Pairs present in given 'ARR'.

For example :
  For the array [50, 21, 9], if we follow 1-based indexing, the Reverse Pairs are (1, 2), (1, 3) and (2, 3). Thus, the total count i.e. the answer becomes 3.
Note :
  A single index of the pair (i, j) can be used multiple times.

Sample Input 1 :
1
6
1 2 3 2 3 1
Sample Output 1 :
2
Explanation Of Sample Input 1 :
Test case 1: 
Given that we follow 1-based indexing, for the array {1, 2, 3, 2, 1}, the pairs satisfying the conditions of Reverse Pairs are 
For i = 3, arr[i] = 3 and for j = 6, arr[j] = 1.
For i = 5, arr[i] = 3 and for j = 6, arr[j] = 1.
Hence there are two possible pairs.
Sample Input 2 :
2
6
6 4 8 2 1 3
5
2 4 3 5 1 
Sample Output 2 :
6
3
Explanation Of Sample Input 2 :
Test case 1: 
Given that we follow 1-based indexing,The possible pairs satisfying the conditions of Reverse Pairs are (1, 4), (1, 5), (2, 5), (3, 4), (3, 5), (3, 6). 
Thus, the answer is 6.

Test case 2: 
Given that we follow 1-based indexing, The possible pair of indices satisfying the above condition are (2, 5), (3, 5), (4, 5). Thus, the answer is 3.

Approach 1 : Brute Force:
    explore array from end n-1 i, and check from begin 0 j til i-1 whether required condition is fulfilled . 
    T.C. : O(N^2)
    S.C. : O(1)

Approach 2: Merge Sort
    As while looking on a test case , might have comeup with an idea what if we have a index and condition is fullfilled and we don't have to go back.
    for i<j, if 0->i is sorted (increasing order) and arr[i] > 2*arr[j] then it will satisfy for elements after j too. 
    But we can't do full sort and then check bcs if ordering is disturbed before calc then all wrong.
    Hence have to look for this approach while sorting. Let's say i>=m and i<=n and sorted and j>=u and j<=v and sorted. and offcourse arr[j] will be sorted 
    in given range we just have to merge, so before merge we can use it for our benefits. As element is above 2 portions are disturbed and sorted but we are checking
    from one set to another which's order's are not altered yet.

#include <bits/stdc++.h> 
int merge(vector<int>&arr, int l, int mid, int h){
	int i = l, j = mid+1, count = 0;
	while(i<=mid && j<=h){
		if(arr[i]>2*arr[j]) count += mid-i+1, ++j ;
		else ++i;
	}
	i=l, j=mid+1;
	int k=0, tmp[h-l+1];
	while(i<=mid && j<=h){
		if(arr[i]<=arr[j]) tmp[k++] = arr[i++];
		else tmp[k++] = arr[j++];
	}
	while(i<=mid) tmp[k++] = arr[i++];
	while(j<=h) tmp[k++] = arr[j++];
	k=0;
	for(int i=l;i<=h;++i) arr[i] = tmp[k++];
	return count;
}
int mergesort(vector<int>&arr, int l, int h){
	int count = 0;
	if(l>=h) return 0;
	int mid = (l+h)/2;
	count += mergesort(arr,l,mid);
	count += mergesort(arr,mid+1,h);
	count += merge(arr, l, mid, h);
	return count;
}
int reversePairs(vector<int> &arr, int n){
	return mergesort(arr,0,n-1);	
}

//T.C. : O(NlogN)
//S.C. : O(N) ( O(N) + O(logN) for stack, as every element is singled out and O(N) as extra array taken)