（*）剑指offer 面试题36：数组中的逆序对

题目：
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

解法：
暴力遍历的方法，直观可行，O(n^2)

基于归并排序的解法：

int inversePairs(int* data, int length) {
   if (data == 0 || length <= 0) return 0;
   int  *copy = new int[length];
   for (int i = 0; i < length; ++i) {
       copy[i] = data[i];
   }
   int cnt = inversePairsCore(data, copy, 0, length - 1);
   delete[] copy;
   
   return cnt;
}

int inversePairsCore(int* data, int* copy, int start, int end) {
   if (start == end) {
       copy[start] = data[start];
       return 0;
   }
   int length = (end - start)/2;
   int left = inversePairsCore(data, copy, start, start + length);
   int right = inversePairsCore(data, copy, start + length + 1, end);
   int i = start + length;
   int j = end;
   int indexCopy = end;
   int cnt = 0;
   while (i >= start && j >= start+length+1) {
       if (data[i] > data[j])  {
           copy[indexCopy--] = data[i--];
           cnt += j - start - length;
       } else {
           copy[indexCopy--] = data[j--];
       }
   }
   for (; i >= start; --i) {
       copy[indexCopy--] = data[i--];
   }
   for (; j >= start+length+1; --j) {
       copy[indexCopy--] = data[j--];
   }
   
   return  left + right + cnt;
}