归并排序

算法思想：

• 归并排序是稳定的，体现在当两个最小指针指向的值相等的时候，要把第一个序列的值输出到结果数组中去。
• 归并排序的时间复杂度是nlogn（logn层，每层n）

代码体现：

int q[N];
int tmp[N];///额外的辅助数组 
void merge_sort(int q[],int l,int r)
{
	if(l>=r) return ;
	int mid = l+r >> 1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;//k是辅助数组中等待安排的下标 
	while(i<=mid&&j<=r)
	{
		if(q[i]<=q[j]) tmp[k++]=q[i++];
		else tmp[k++]=q[j++];
	}
	while(i<=mid) tmp[k++]=q[i++];
	while(j<=r) tmp[k++]=q[j++];
	for(i = l,j = 0;i <= r;i++,j++) q[i]=tmp[j];
}

归并排序求逆序对数量

算法思想：

代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int q[N];
int tmp[N];
LL merge_sortre(int l,int r)
{
	if(l>=r) return 0;
	int mid=(l+r)>>1;
	LL res=merge_sortre(l,mid)+merge_sortre(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r)
	{
		if(q[i]<=q[j])	tmp[k++]=q[i++];
		else 
		{
			tmp[k++]=q[j++];
			res +=mid-i+1;
		}
	}
	while(i<=mid) tmp[k++]=q[i++];
	while(j<=r) tmp[k++]=q[j++];
	for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
	return res;
} 

归并排序与归并排序求逆序对数量

原文：https://www.cnblogs.com/codertea/p/12798162.html