參考資料：
[1]https://blog.csdn.net/yuehailin/article/details/68961304(講的真好)
[2]http://www.cnblogs.com/skywang12345/p/3602369.html
//歸并排序
#include<iostream>
using namespace std;
void merge(int* a,int start,int mid,int end)
{
int* tmp = new int[end-start+1];//定義1個臨時的區(qū)域
int i= start;//第一個有序區(qū)索引
int j = mid+1;//第二個有序區(qū)索引
int k = 0;//臨時區(qū)域索引
while(i<=mid && j<=end)
{
if(a[i]<=a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
}
//ｉ芟！Ｖ寐摺当辐！如果其中一個有序區(qū)空了嘴脾，那么直接填進(jìn)行就可以
while(i<=mid)
{
tmp[k++]=a[i++];
}
while(j<=end)
{
tmp[k++] =a[j++];
}
//將排序后的元素，全部整合到a中
for(i=0;i<k;i++)
{
//!!!!!start
a[start+i]=tmp[i];
}
delete[] tmp;
}
void mergeSort(int* a,int start,int end)
{
if(start >= end)//如果就一個數(shù)，那是不行的!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
return;
//比如 5崔赌，7漆际，3淆珊，6分為兩個序列5，7和6奸汇，8
int mid = (start+end)/2;
//步驟1：使左邊序列變?yōu)橛行蛐蛄? mergeSort(a,start,mid);
//步驟2：使右邊序列變?yōu)橛行蛐蛄? mergeSort(a,mid+1,end);
//步驟3：合并兩個有序序列
merge(a,start,mid,end);
}
int main()
{
int a[]={40,20,30,10,60,50};
//數(shù)組的長度
int ilen=sizeof(a)/sizeof(a[0]);
cout<<"before insert sort"<<endl;
for(int i=0;i<ilen;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
//查了一下午mergeSort(a,0,ilen)是錯的Ｊ┓！＠拚摇４亮摺！Ｓね荨９强印！！；锻佟Ｇ揖！礁遣！
mergeSort(a,0,ilen-1);
cout<<"after insert sort"<<endl;
for(int i=0;i<ilen;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
歸并排序的時間復(fù)雜度：NlogN
