夜深人静写算法——合并排序（递归）

合并排序：
采用分治的方法。

第一步：

(1) 将数组分成两部分

(2)然后将分开的数组当成一个新的数组 ，重复操作(1)，直到数组的大小为1.

第二步：
将分开的已排好的小数组进行合并（按照一定的顺序）。

因为最小的数组的大小为1，然后进行合并的排序，所以可以保证小数组总是排好序的

#include <stdio.h>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;

template <class Type>
void Merge(Type a[MAX],int left1,int right1,int left2,int right2)//合并两个数组 
{         //将数组a的第left1到第right1 和 数组a的第left2到right2 进行合并

	int str1 = left1,str2 = left2; 
	int length  = 0 ;
	Type b[MAX];
	
	while(str1 <= right1 && str2 <= right2){
		if(a[str1] < a[str2]){
			b[length++] = a[str1++];
		 
		}else
			b[length++] = a[str2++];	 
	}
	
	if(str1 <= right1)
		for(int i = str1; i <= right1 ; i++)
			b[length++] = a[i];
	else if( str2 <= right2)
		for(int i = str2; i <= right2; i++)
			b[length++] = a[i];
	
 
	for(int i = left1 ; i < left1 + length; i++ ) //将合并好的数组b复制到a的原始位置（left1到right2）
		a[i] = b[i - left1] ;
	
	
} 

template <class Type>
void Mergesort(Type a[MAX],int left,int right){
	if(left < right){  //数组的大小至少为2
		int j= (left + right)/2; //将数组分为两部分，
		Mergesort(a,left,j); 
		Mergesort(a,j+1,right);
		Merge(a,left,j,j+1,right); //合并
	}
}
int main(){
	int a[10] = { 2,1,5,4,3,7,6,8,9,0};
	
	for(int i = 0; i <10 ; i++){
		cout<<a[i];
		if(i!= 9)cout<<" ";
		else cout<<endl;
	}
	
	Mergesort(a,0,9);
	
	cout<<"排序后\n"; 
	for(int i = 0; i <10 ; i++){
		cout<<a[i];
		if(i!= 9)cout<<" ";
		else cout<<endl;
	}
	
	return 0;	
	
}