1.20归并排序

#include<stdio.h>
#include<stdlib.h>
int a[15000];
int tmp[15000];
long long merge_sort(int l,int r)
{
	//printf("l=%d r=%d\n",l,r);
	if(l>=r) return 0;
	int mid=(l+r)>>1;
	long long res=merge_sort(l,mid)+merge_sort(mid+1,r);

	int i=l;int j=mid+1;int k=0;//三个指针 
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j]) 
		{
			tmp[k]=a[i];
			k++;i++; 
		}
		else
		{
			//printf("a[%d]=%d a[%d]=%d\n",i,a[i],j,a[j]);
			res+=mid-i+1;
			tmp[k]=a[j];
			k++;j++;
		}
	}
	while(i<=mid) 
	{
		tmp[k]=a[i];k++;i++;
	}
	while(j<=r)
	{
		tmp[k]=a[j];k++;j++;
	}
	for(i=l;i<=r;i++) a[i]=tmp[i-l];
	return res;
}
int main()
{
	int n;int i;
	scanf("%d",&n);
	for(i=0;i<=n-1;i++) scanf("%d",&a[i]);
	long long ans=merge_sort(0,n-1);
	printf("%I64d\n",ans);
	return 0; 
}