[C++知识库]归并排序-C++ 易理解版本

归并排序 时间复杂度O(nlog^n) 稳定 空间复杂度O(n+log^n)

void Merge(vector<int>& v3, vector<int>& v2, int l, int m, int r)
{
	int i=l,j=m+1,k=l;
	while(i<=m && j<=r)
	{
		v2[k++] = v3[i] < v3[j] ? v3[i++]:v3[j++];
	}
	while (i<=m)
	{
		v2[k++] = v3[i++];
	}
	while (j<=r)
	{
		v2[k++] = v3[j++];
	}
}

void Msort(vector<int>& br, vector<int>& v2,int l, int r)
{
	int n = br.size();
	vector<int> v3(n);
	if (l == r) {   v2[l] = br[l];}
	else
	{
	int m = (l+r)/2;
	Msort(br,v3,l,m);
	Msort(br,v3,m+1,r);
	Merge(v3,v2,l,m,r);
	}
}

void MergeSort(vector<int>& v1,vector<int>& v2 )
{
	int n=v1.size();
	Msort(v1,v2,0,n-1);
}

int main()
{
	int arr[] = {2,5,1,4,9,8,10};
	vector<int> ans(arr,arr+7);
	vector<int> res(7);
	MergeSort(ans,res);
	for (auto&s:res)
	{
		cout<<s<<endl;
	}
}

运行结果如下：