归并排序求逆序对数

参考博客：归并排序求逆序对数

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
//归并排序是借助一个辅助数组来进行排序 
int ans = 0;
void merge_sort(int *A, int l, int r, int *T) {//A是原数组，T是辅助数组 
if(r-l>1){
int mid = (l+r)/2;
merge_sort(A, l, mid, T);
merge_sort(A, mid, r, T);
int p = l , q = mid;
int i = l;
while(p < mid || q < r) {
//右边空了或左边还有数并且左边接下来的第一个数小
if(q >= r || (p<mid && A[p]<A[q]))  T[i++] = A[p++];
else {
ans += mid-p; //求逆序对数 
T[i++] = A[q++]; 
}
//左边空了或右边还有数并且右边接下来的第一个数小 
}
for(i = l; i < r; i++) A[i] = T[i];  //从辅助空间复制回A数组  这时都是排好序的 
}
else return ;//如果r-l<=1说明区间元素等于或少于1个自然就返回，将这个作为边界 
}

int main() {
int a[] = {8, 7, 6, 5, 4, 3, 2, 1};
int t[8];
merge_sort(a, 0, 8, t);
for(int i = 0; i < 8; i++) {
cout << a[i] << " ";
} 
cout << endl;
cout << ans << endl;
return 0; 
}