归并排序（分治法）

归并排序，涉及到两个函数，一个函数merger()负责把两个有序的子序列合并成一个有序的子序列，另外一个函数tomany()是负责把子序列排序，是采用分治的思想排序。首先把子序列分成一个，都是有序的，两个通过递归调用merger()，也能使他有序，因为一个是有序的，merger()能使两个有序的，大小为1的子序列合并成一个大小为2的子序列，由此可见扩展成4，8，16个都能使之有序。

代码如下：

#include<stdio.h>
#define size 10
void merger(int a[],int start,int mid,int end);
void tomany(int a[],int start,int end);
void main()
{

    int a[size]= {12,2,321,144,45,51,45,5,13,9};
    tomany(a,0,size-1);
    for(int i=0; i<size; i++)
        printf("%d\t",a[i]);

}
void merger(int a[],int start,int mid,int end)
{

    int temp[size]= {0};//初始化临时数组，存放合并的子序列
    int i=start;//子序列头
    int j=mid+1;//中间分割点
    int k=start;//子序列尾
    while(i<mid+1&&j<=end)//两个序列都没到尾
    {

        if(a[i]<a[j])
        {

            temp[k]=a[i];
            k++;
            i++;
        }
        else
        {

            temp[k]=a[j];
            k++;
            j++;
        }


    }
    while(i==mid+1&&j<=end)//前面那个到尾了，后面没到尾，没到尾的部分追加到temp[]上面去
    {

        temp[k]=a[j];
        j++;
        k++;
    }
    while(j==end+1&&i<mid+1)//后面到尾了，前面没到尾，全部追加上去
    {

        temp[k]=a[i];
        i++;
        k++;
    }
    for(int p=start; p<end+1; p++)
        a[p]=temp[p];

}
void tomany(int a[],int start,int end)
{

    int mid=(start+end)/2;
    if(start!=end)//直到子序列大小为1
    {

        tomany(a,start,mid);
        tomany(a,mid+1,end);
        merger(a,start,mid,end);
    }

}