归并排序（Merge Sort）是一种分治算法，其基本思想是将一个数组分成两半，分别对这两半进行排序，然后再将这两个有序的半数组合并成一个有序的完整数组。这个过程是递归进行的，直到数组中的每个元素都成为一个有序的子数组。以下是归并排序算法的步骤：
主要步骤
1. 分解（Divide）：
- 如果数组的长度大于1，那么将数组分成两个子数组，每个子数组的长度大约是原数组长度的一半。
2. 解决（Conquer）：
- 对两个子数组分别进行归并排序，这个过程是递归进行的。
3. 合并（Combine）：
- 将两个已排序的子数组合并成一个有序数组。在合并过程中，逐个比较两个子数组的元素，将较小的元素放入新数组中，直到所有元素都被合并。
归并排序的关键在于合并步骤，它确保了最终数组的有序性。以下是合并步骤的详细描述：
- 初始化两个指针，分别指向两个子数组的起始位置。
- 比较两个指针所指向的元素，将较小的元素复制到新数组中，并将该指针向前移动一位。
- 重复上述步骤，直到一个子数组的所有元素都被复制到新数组中。
- 将另一个子数组中剩余的元素复制到新数组中，因为它们已经是有序的。
归并排序的时间复杂度为O(n log n)，其中n是数组的长度。这是因为每次分解都将数组分成两半，需要log n次分解，每次合并操作需要O(n)的时间。
在归并排序的过程中，还可以计算数组中的逆序对数量。逆序对是指数组中元素对(i, j)，满足i < j但a[i] > a[j]。在合并步骤中，当从右侧子数组中取元素时，左侧子数组中所有尚未处理的元素都比右侧子数组的当前元素大，因此它们与右侧子数组的当前元素形成了逆序对。通过在合并过程中累加这些逆序对的数量，可以得到整个数组的逆序对总数。
模板代码
求逆序对
#include<bits/stdc++.h>
using namespace std;
// 定义一个整型数组a，其大小为100001，用于存储输入的整数序列
int a[100001];
// 定义一个长整型变量sum，用于存储逆序对的数量
long long sum=0;
// 定义一个递归函数merge，用于合并两个有序序列，并计算逆序对的数量
void merge(int ll,int rr){
// 定义一个临时数组t，用于存储合并后的序列
int t[100001];
// 如果序列的长度小于等于1，则不需要合并
if(rr -ll <=1) return ;
// 计算中间索引
int mid = ll +(rr-ll)/2;
// 递归地合并左半部分序列
merge(ll,mid);
// 递归地合并右半部分序列
merge(mid,rr);
// 初始化两个指针p和q，分别指向左半部分和右半部分序列的起始位置
// 初始化一个指针s，用于指向临时数组t的当前位置
int p=ll,q=mid,s=ll;
// 合并两个有序序列，并计算逆序对的数量
while(s < rr){
// 如果左半部分序列已经全部合并，或者右半部分序列的当前元素小于左半部分序列的当前元素
if(p>=mid ||(q < rr && a[p]>a[q])){
// 将右半部分序列的当前元素复制到临时数组t中
t[s++]=a[q++];
// 更新逆序对的数量
sum+=mid-p;
}else{
// 将左半部分序列的当前元素复制到临时数组t中
t[s++]=a[p++];
}
}
// 将临时数组t中的元素复制回原数组a中
for(int i=ll;i<rr;i++) a[i]=t[i];
}
// 主函数
int main(){
// 读取整数序列的长度
int n;
cin >> n;
// 读取整数序列
for(int i=0;i<n;i++){
cin >> a[i];
}
// 调用merge函数，合并整数序列，并计算逆序对的数量
merge(0,n);
// 输出逆序对的数量
cout << sum;
// 返回0，表示程序正常结束
return 0;
}