利用归并排序的特点，对一个区间的逆序对进行快速计算。

归并排序的非递归写法，建立一个grap来控制区间大小，由小到大完成归并排序；没有建立栈帧的消耗。

class Solution {
public:
    //归并非递归
    int _MergeSort(vector<int>& data, int n)
    {
        int count = 0;
        vector<int> tmp(data.size(),0);
        //用grap表示一个个小区间，然后迭代大区间进行归并
        //利用grap把序列分成小区间进行比较归并
        int grap = 1;
        //最后一个左区间大于序列长度就说明全部有序了
        while(grap < n)
        {
            //分割成一个一个小区间比较，迭代
            for(int i = 0; i < n; i += 2 * grap)
            {
                //左区间
                int begin1 = i, end1 = i + grap - 1;
                //右区间
                int begin2 = i + grap, end2 = i + 2 * grap - 1;
                //如果只有左区间了，说明全部有序直接跳出
                if(begin2 > n)
                    break;
                //左区间不完整或者右区间不完整直接修改结束位置
                if(end2 > n)
                    end2 = n - 1;
                //中间数组的下标开始的位置一定是跟i一样的，不会覆盖到其他区间的数据
                int j = i;
                //两个区间比较形成有序，借助第三方数组
			    //有一个区间结束就结束
                while(begin1 <= end1 && begin2 <= end2)
                {
                    //前面都跟归并排序的思想一致
                    //这里判断是解题的关键
                    if(data[begin1] > data[begin2])
                    {
                        //前面的数比后面的大，就是逆序对
                        //小的先进存数据的数组，排成升序
                        tmp[j++] = data[begin2++];
                        //左区间也是升序，说明左区间后面的数都可以和右区间这个数组成逆序对
                        count += (end1 - begin1 + 1);
                        //防止溢出
                        count %= 1000000007;
                    }
                    else
                        tmp[j++] = data[begin1++];
                        
                }
                //结束后把另外一个没有拷贝完成的区间的数拷拷贝
                while(begin1 <= end1)
                    tmp[j++] = data[begin1++];
                while(begin2 <= end2)
                    tmp[j++] = data[begin2++];
                //写入原来的数组保持区间有序
                //继续迭代
                for(int z = i; z <= end2; ++z)
                    data[z] = tmp[z];
            }
            //扩大grap，增大比较区间
            grap *= 2;
        }
        return count;
    }
    int InversePairs(vector<int> data) {
        return _MergeSort(data,data.size()) ;
    }
};