分治策略中有一个经典的算法就是合并排序，这个算法的精髓也是分治二字，分而治之。将一个大规模的问题分割成若干个同样的小问题，小问题的规模很小，很容易解决，解决了小的问题后再对这些小问题的结果进行合并得到大规模问题的解答。

合并排序便是分治策略中比较经典的算法，首先是合并，两个排列有序的数列经过合并后成为有序的数组：代码如下:

void _merge(int *A,int left,int middle,int right)
{
	int i=left,j=middle+1,k=0;
	int *C;
	C=new int[right-left+1];
	while(i<middle+1 && j<right+1)
	{
		if(A[i]<A[j])
		{
			C[k++]=A[i++];
		}
		else
		{
			C[k++]=A[j++];
		}
	}
	while(i<middle+1)
		C[k++]=A[i++];
	while(j<right+1)
		C[k++]=A[j++];
	for(int i=0;i<right-left+1;i++)
	{
		A[i+left]=C[i];
	}
	delete[] C;
}

void _merge_sort(int *A,int left,int right)
{
	
	if(left<right)
	{
		int middle=(left+right)/2;
		_merge_sort(A,left,middle);
		_merge_sort(A,middle+1,right);
		_merge(A,left,middle,right);
	}
}

void main()
{
	int ib[]={2,3,1,0,9,1,3,5};
	int length=sizeof(ib)/sizeof(int);
	_merge_sort(ib,0,length-1);
	for(int i=0;i<length;i++)
	{
		cout<<ib[i]<<' ';
	}
}