（分治法）归并排序

分治算法一般分为如下3个步骤。

划分问题：把问题的实例划分成子问题。
递归求解：递归解决子问题。
合并问题：合并子问题的解得到原问题的解。

归并排序

按照分治三步法，对归并排序算法介绍如下。
划分问题：把序列分成元素个数尽量相等的两半。
递归求解：把两半元素分别排序。
合并问题：把两个有序表合并成一个。

借鉴一下https://blog.csdn.net/yuehailin/article/details/68961304
的思想：

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

更简洁的代码：

#include<iostream>
using namespace std;
void merge_sort(int *a,int x,int y,int *t){
    if(y-x>1){
        int m=x+(y-x)/2;
        int p=x,q=m,i=x;
        merge_sort(a,x,m,t);
        merge_sort(a,m,y,t);
        while(p<m||q<y){
            if(q>=y||(p<m&&a[p]<=a[q]))
            t[i++]=a[p++];
            else t[i++]=a[q++];
        }
        for(int i=x;i<y;i++) a[i]=t[i];
    }
} 

int main(){
    int a[100],b[100];
    for(int i=0;i<10;++i)
    {
        cin>>a[i];
    }
    merge_sort(a,0,10,b);
    for(int i=0;i<10;++i){
        cout<<b[i]<<' ';
    }
}

分析一下这个代码的意思：
if(q>=y||(p < m && a[p] < =a[q]))
这个意思是说，如果右边的数组为空或者左边数组不为空，而且左边的数小于右边，那么就把左边的这个数放到临时空间
整体上来说，先递归成一个数，然后再进行合并