Reverse Pairs

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.

2. All the numbers in the input array are in the range of 32-bit integer.

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        int leftAns = mergeSort(nums, start, mid);
        int rightAns = mergeSort(nums, mid + 1, end);
        return leftAns + rightAns + merge(nums, start, end);
    }

    public int merge(int[] nums, int start, int end) {
        int mid = start + (end - start) / 2;
        int p1 = start, p2 = mid + 1;
        int pointer = mid + 1, index = 0, count = 0;
        int[] temp = new int[end - start + 1];
        while (p1 <= mid) {
            // All the elements behind pointer, are satisfying the equation with "p1"
            while (pointer <= end && 2L * nums[pointer] < (long) nums[p1])
                pointer++;
            count += pointer - (mid + 1);
            while (p2 <= end && nums[p2] < nums[p1])
                temp[index++] = nums[p2++];
            temp[index++] = nums[p1++];
        }
        while (p2 <= end)
            temp[index++] = nums[p2++];
        for (int i = start; i <= end; i++)
            nums[i] = temp[i - start];
        return count;
    }
}