题解 | #数组中的逆序对#

class Solution {
public:
    int MergeSort(vector <int> &arr, vector <int> &temp, int low, int high) {
		// 停止划分
		if (low >= high)	return 0;
		int mid = (low + high) / 2;
		long count = MergeSort(arr, temp, low, mid) + MergeSort(arr, temp, mid + 1, high);
		int i,j,k;
		for (k = low; k <= high; ++k) {
			temp[k] = arr[k];
		}
		
		for (i = mid, j = high, k = high; i >= low && j > mid; --k) {
			if (temp[i] >= temp[j]) {
				arr[k] = temp[i];
				i--;
				count = count + j - mid;
			}
			else {
				arr[k] = temp[j];
				j--;
			}
		}
		while (i >= low) {
			arr[k] = temp[i];
			k--;	i--;
			}
		while (j > mid) {
			arr[k] = temp[j];
			k--;	j--;
		}
		return count % 1000000007;
	}
    int InversePairs(vector<int> data) {
		vector <int> temp(data.size());
		return MergeSort(data, temp, 0, data.size() - 1);
    }
};