归并排序

#include<iostream>
#define N 500
using namespace std;
int num[N];
int temp[N];

void Merge(int begin,int mid,int end) {
	int k=begin,i=begin,j=mid+1;
	while(i!=mid+1 && j!=end+1) {
		if(num[i]>num[j])
			temp[k++]=num[j++];
		else
			temp[k++]=num[i++];
	}
	int tp=0;
	while(i!=mid+1) temp[k++]=num[i++];
	while(j!=end+1) temp[k++]=num[j++];
	for(int l=begin;l<=end;l++)
		num[l]=temp[l];
	
}

void MSort(int begin,int end) {
	int mid;
	//这里也和课本上的不太一样，因为其实相等的话就不用再操作了，直接到下一步，然后合并就行了
	if(begin<end) {
		mid=(begin+end)/2;
		MSort(begin,mid);
		MSort(mid+1,end);
		Merge(begin,mid,end);
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=0; i<n; i++)
		cin>>num[i];
	MSort(0,n-1);
	for(int i=0; i<n; i++)
		cout<<num[i]<<' ';
	return 0;
}