归并排序.cpp

来自「数值分析中常用的几种算法的实现」· C++ 代码 · 共 74 行

int n,inverse;
void mergesort(int a[],int b[],int len){
	int i,j,k,t,left;
	i=0;
	t=0;
	while(i+2*len<n){
		left=len;
		j=i;
		k=i+len;
		while(j<i+len&&k<i+2*len){
			if(b[j]>b[k]){
				inverse+=left;
				a[t++]=b[k];
				k++;
			}
			else{
				a[t++]=b[j];
				j++;
				left-=1;
			}
		}
		while(k<i+2*len){
			a[t++]=b[k];
			k++;
		}
		while(j<i+len){
			a[t++]=b[j];
			j++;
		}
		i+=2*len;
	}
	if(i+len<n){
		j=i;
		k=i+len;
		left=len;
		while(j<i+len&&k<n){
			if(b[j]>b[k]){
				inverse+=left;
				a[t++]=b[k];
				k++;
			}
			else{
				a[t++]=b[j];
				j++;
				left-=1;
			}
		}
		while(k<n){
			a[t++]=b[k];
			k++;
		}
		while(j<i+len){
			a[t++]=b[j];
			j++;
		}
		i+=2*len;	
	}
	else{
		while(i<n){
			a[t++]=b[i];
			i++;
		}
	}
	return;
}
void merge(int a[]){
	int temp[700];
	int len=1;
	while(len<n){
		mergesort(temp,a,len); len*=2;
		mergesort(a,temp,len); len*=2;
	}
	return;
}