Thanks to @Pepsi's solution of 327. Count of Range Sum. My code below is so similar with the one Pepsi posted here.

@Chidong's solution with BST is really impressive, but I think because it *may not be a balanced tree*, his solution maybe not *strictly* O(nlogn), but **merge sort** can do it with **worst case time complexity** in **O(nlogn)**, so that my solution could beat 100%. That's just my guess. please let me know if I am wrong.

```
public class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int l, int r) {
if (l >= r) return 0;
int mid = l + (r - l)/2;
int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
int[] cache = new int[r - l + 1];
int i = l, t = l, c = 0;
for (int j = mid + 1; j <= r; j++, c++) {
while (i <= mid && nums[i] <= 2 * (long)nums[j]) i++;
while (t <= mid && nums[t] < nums[j]) cache[c++] = nums[t++];
cache[c] = nums[j];
count += mid - i + 1;
}
while (t <= mid) cache[c++] = nums[t++];
System.arraycopy(cache, 0, nums, l, r - l + 1);
return count;
}
}
```