基本原理

归并排序运用了分治的思想，先将数组二分成一个元素（一个元素时看为有序），然后将这些元素不断合并，每合并一次排一次序，最后就可以得到有序的数组。

比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段：12 ,23,1,44 和 233,10,9,8，
发现还能再分成4段：12 ,23 和 1,44———233,10 和 9,8。
再分成8段：12—23—1—44 和233—10—9—8。
这时候开始把子序列进行排序合并，一个元素就是有序的。所以不用排序。
合并成2个一组排序得到：12，23——1，44—-10，233—-8，9。
再合并成4个一组排序得到：1，12，23，44—-8，9，10，233。
最后合并得到最终结果：1，8，9，10，12，23，44，233。

合并过程看代码

链接：https://www.jianshu.com/p/b50a6034eb90

图解

这个图片蓝色部分就是拆的过程，而绿的部分为并的过程

代码实现

void paixu(int first,int mid,int last,int a[],int temp[])//这是合并过程
{
    int l1=first,l2=mid+1,r1=mid,r2=last;
    int k=0;
    while(l1<=r1&&l2<=r2)//两部分都存在时看哪个小就加上哪个
    {
        if(a[l1]<=a[l2])
        {
            temp[k++]=a[l1++];
        }
        else
        {
            temp[k++]=a[l2++];
        }
    }
    while(l1<=r1)//第一部分有剩余就把第一部分剩下的全加上
    {
        temp[k++]=a[l1++];
    }
    while(l2<=r2)
    {
        temp[k++]=a[l2++];
    }
    for(int i=0;i<k;i++)
    {
        a[i+first]=temp[i];
    }
}
void xunhuan(int first,int last,int a[],int temp[])
{
    if(first<last)
    {
        int mid=(first+last)/2;
        xunhuan(first,mid,a,temp);//拆左边
        xunhuan(mid+1,last,a,temp);//拆右边
        paixu(first,mid,last,a,temp);//合并
    }
}
bool mergesort(int a[],int first,int last)
{
    int* p=new int[last-first];//建一个临时数组，合并时用
    if(p==NULL)//判断是否传入空数组
    {
        return false;
    }
    xunhuan(first,last,a,p);
    delete [] p;
    return true;
}