归并排序（merge sort）

归并排序
归并排序是一种递归排序算法，无论数组元素的原始顺序如何，其性能恒定不变。将数组一分为二，分别排序两部分元素，再将有序的两半数组归并为一个有序数组。归并步骤比较数组前一半的元素与数组的后一半元素，并将较小元素移到临时数组，该过程继续前进，直到其中一半再没有元素为止。此后只需将其余元素移到临时数组即可。最后将临时数组复制到原始数组。

#include<iostream>
using namespace std;
void sort(int arr[],int first,int last);
void merge(int arr[],int first,int mid,int last);
int main()
{
	const int SIZE=10;
	int aarray[SIZE]={4,8,9,6,3,2,15,7,1,12};
	for(int i=0;i<SIZE;i++)
		cout<<"the "<<i+1<<"th item is"<<aarray[i]<<endl;
	sort(aarray,0,SIZE-1);
	cout<<"the sorted array aarray is :"<<endl;
	for(int i=0;i<SIZE;i++)
		cout<<"the "<<i+1<<"th item is "<<aarray[i]<<endl;
	return 0;
}
void merge(int arr[],int first,int mid,int last)
{
	int temp[last-first+1];
	int first1=first;
	int last1=mid;
	int first2=mid+1;
	int last2=last;
	int i=0;
	for(;(first1<=last1)&&(first2<=last2);i++)
	{
		if(arr[first1]<arr[first2])
		{
			temp[i]=arr[first1];
			first1++;
		}
		else
		{
			temp[i]=arr[first2];
			first2++;
		}
	}
	for(;first1<=last1;first1++,i++)
		temp[i]=arr[first1];
	for(;first2<=last2;first2++,i++)
		temp[i]=arr[first2];
	for(int i=0;i<=last-first;i++)
		arr[i+first]=temp[i];
}
void sort(int arr[],int first,int last)
{
	if(first<last)
	{
		int mid=(first+last)/2;
		sort(arr,first,mid);
		sort(arr,mid+1,last);
		merge(arr,first,mid,last);

	}
}