归并排序

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。

举例：合并数列(1，3，5)与(2，4)的时候
1．先取出前面数列中的1。
2．然后取出后面数列中的2，明显！这个2和前面的3，5都可以组成逆序数对即3和2，5和2都是逆序数对。
3．然后取出前面数列中的3。
4．然后取出后面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N * LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)

综上得知：每一次合并，只要使用后面的数列中的数，那么此数的逆序对数就为前面数列中剩下数的个数

static NSInteger count = 0;//记录逆序对数

+(void)merge:(NSMutableArray *)arr lo:(NSInteger)lo mid:(NSInteger)mid hi:(NSInteger)hi
{
NSMutableArray *tmpArr = [arr mutableCopy];
NSInteger i = lo;
NSInteger j = mid+1;
count = 0;
for (NSInteger k=lo; k<=hi; k++) {
if (i>mid) {
arr[k] = tmpArr[j++];
}
else if(j>hi)
{
arr[k] = tmpArr[i++];
}
else if([arr[i]integerValue]<[arr[j]integerValue])
{
arr[k] = tmpArr[i++];
}
else
{
arr[k] = tmpArr[j++];
count += i - lo + 1;
}
}
}

+(void)sort:(NSMutableArray )arr lo:(NSInteger)lo hi:(NSInteger)hi
{
if (lo>=hi) {
return;
}
NSInteger mid = lo + (hi-lo)0.5;
[self sort:arr lo:lo hi:mid];
[self sort:arr lo:mid+1 hi:hi];
[self merge:arr lo:lo mid:mid hi:hi];
}