歸并排序 C++ 模闆

歸并排序的使用和了解在于分和治，利用遞歸我們可以輕松實作

歸并排序時間複雜度低，且在分，治過程中可以進行一些變形，用于逆序對求解等問題

#include<iostream>
using namespace std;
const int maxn=1e5;
int tmp[maxn],q[maxn];
void _merge(int l,int r){
	if(l==r)	return;
	int mid=(l+r)>>1;
	_merge(l,mid);
	_merge(mid+1,r);
	int i=l,j=mid+1,k=l;
	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;i<=r;i++)	q[i]=tmp[i];
	return;
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)	cin>>q[i];
	_merge(1,n);
	for(int i=1;i<=n;i++)	cout<<q[i]<<" ";
}