【算法】合并排序的递归实现算法

基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

合并排序的递归实现算法。

输入：先输入进行合并排序元素的个数，然后依次随机输入（或随机生成）每个数字。

输出：元素排序后的结果，数字之间不加任何标识符。

示例：输入：8  11  1  2  4  8  6  15  8，输出：1  2  4  6  8  8  11  15

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;
int b[maxn];

void merge(int a[],int left,int mid,int right){//merge可在O(n)时间内完成
	int i=left,j=mid+1; 
	int k=left; 
	while(i<=mid&&j<=right){
		if(a[i]>=a[j])b[k++]=a[j++];
		else b[k++]=a[i++];
	}
	//比完了之后剩余的依次存下 
	if(i>mid)for(int q=k;q<=right;q++)b[k++]=a[j++];
	else for(int q=k;q<=right;q++)b[k++]=a[i++];
	//将合并后的数组段再复制回数组a中
	for(int i=left;i<=right;i++)a[i]=b[i];
	
}

void sort(int a[],int left,int right){
	if (left<right){//至少有2个元素
		int mid=(left+right)/2;//取中点
		sort(a,left,mid);
		sort(a,mid+1,right);
		merge(a,left,mid,right);//合并两个排好序的数组段到一个新的
	}
}



int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,0,n-1);
	for(int i=0;i<n;i++)cout<<a[i]<<" ";
	return 0;	
}