归并排序：
一种稳定的算法，时间复杂度可以达到nlogn
是比较快的一种算法，并且稳定，这是最重要的一点，这点事区别于快速排序算法的。
归并算法的核心思想是：
分治。
对一个无序数组来说，唯一有序的地方就是每个数，也就是说，每个数对于它自身都是有序的。
所以我们可以这么做。
把一个数组，比如有n个元素，
我们把它分成n个部分
然后两两归并。
就剩下n/2个数组。
再重复以上过程，就是递归。
对了，每次归并的过程，你要准备一个新的数组把原来数组的存到里面，最后再放回去。
代码如下：（PS ： 很经典的算法，自己联系实现吧）
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
void mergearray(int array[],int start,int mid,int end,int p[]){
int i=start,im=mid;
int j=mid+1,jm=end;
int k=0;
while(i<=im && j<=jm){ // 千万不能写成 ||
if(array[i]<array[j]){
p[k++]=array[i++];
}
else{
p[k++]=array[j++];
}
}
while(i<=im){
p[k++]=array[i++];
}
while(j<=jm){
p[k++]=array[j++];
}
for(int i=0;i<k;i++){
array[start+i]=p[i];
}
}
void mergesort(int array[],int start,int end,int p[]){
if(start < end){
int mid = (start+end)/2;
mergesort(array,start,mid,p);
mergesort(array,mid+1,end,p);
mergearray(array,start,mid,end,p);
}
}
bool merge(int array[],int n){
int *p = new int[n];
if(p==NULL) return false;
mergesort(array,0,n-1,p);
delete[] p;
p = NULL;
}
int main(){
int array[100];
srand(time(NULL));
for(int i=0;i<100;i++){
array[i]=rand()%101;
}
merge(array,100);
for(int i=0;i<100;i++){
cout<<array[i]<<‘ ‘;
if((i+1)%10==0) cout<<endl;
}
return 0;
}