1.算法思想（分治法）
-分治法
将问题分解为几个规模较小但是类似的子问题，递归地求解这些子问题，然后将这些子问题合并。
-分治法的基本模式
分解：将原问题分解为若干个子问题，这些子问题是原问题的规模较小的问题，求解方法与原问题一致。
解决：递归的去求解，当问题规模足够小时可以直接求解。
合并：将子问题的解合并成原问题的解，这一过程不同的问题方法各不相同。
-分治法在归并排序中的应用
分解：将待排序的n个元素分成各具有n/2个元素的子序列。
解决：当子序列只有一个元素时（子问题规模足够小），该序列已经排好。
合并：合并两个已经排好序的序列，直到合并成一个序列。
2.算法实现
-合并算法
两个待排的序列可以看成两堆按大小排列好的扑克牌，最小的扑克牌在牌堆的最上面，现在将两堆扑克牌合并。只要将两个牌堆最上面的两张牌比较大小，取较小的牌置于新的牌堆上。直到一个牌堆为空时，将另一个牌堆直接放到新牌堆上即可。这里在代码实现时，使用了哨兵节点，也就是在牌堆底部加上一张最大的牌，这样不会出现牌堆为空的现象。结束的判断则变成了，比较次数的判断，假设一共有n张牌，则需要比较n-1次。

• 代码实现

void merge(int *A,int start,int mid,int end){
//这里的mid是两个待排序列的分界位置，可以合并两个不等长的序列
    int *array1,*array2;
    int length1,length2;
    int i,j,k;
    length1=mid-start+1;
    length2=end-mid;
    array1=malloc(sizeof(int)*(length1+2));
    array2=malloc(sizeof(int)*(length2+2));
    //array1和array2是申请的存放已排好序列的两个数组，因为要放置哨兵，并从1的位置开始存储数据，故需要申请length+2个空间
    for(i=1;i<=length1;i++){
        array1[i]=A[start+i-1];
    }
    for(j=1;j<=length2;j++){
        array2[j]=A[mid+j];
    }
    //将待排数据放入申请的数组中
    array1[length1+1]=INT_MAX;
    array2[length2+1]=INT_MAX;
    //设置哨兵节点，这里直接使用INT_MAX
    for(i=1,j=1,k=start;k<=end;k++){
        if(array1[i]<=array2[j]){
            A[k]=array1[i];
            i++;
        }
        else{
            A[k]=array2[j];
            j++;
        }
    }
    //这里的for循环就是在比较当前位置两个数组中数的大小。
    free(array1);
    free(array2);
}

-递归归并算法
将数组不断的二分，直到全部分为只有一个元素的序列，既可以递归返回两两合并。

• 代码实现

void merge_sort(int *A,int start,int end){
    int mid;
    if(start<end){
        mid=(start+end)/2;
        merge_sort(A,start,mid);
        merge_sort(A,mid+1,end);
        merge(A,start,mid,end);
    }
}
//简单的二分，只要长度大于1就2分，全部2分完毕再递归返回合并。

附：整体代码（无注释）

#include <stdio.h>
#include <stdlib.h>

void merge(int *A,int start,int mid,int end){
    int *array1,*array2;
    int length1,length2;
    int i,j,k;
    length1=mid-start+1;
    length2=end-mid;
    array1=malloc(sizeof(int)*(length1+2));
    array2=malloc(sizeof(int)*(length2+2));
    for(i=1;i<=length1;i++){
        array1[i]=A[start+i-1];
    }
    for(j=1;j<=length2;j++){
        array2[j]=A[mid+j];
    }
    array1[length1+1]=INT_MAX;
    array2[length2+1]=INT_MAX;
    for(i=1,j=1,k=start;k<=end;k++){
        if(array1[i]<=array2[j]){
            A[k]=array1[i];
            i++;
        }
        else{
            A[k]=array2[j];
            j++;
        }
    }
}

void merge_sort(int *A,int start,int end){
    int mid;
    if(start<end){
        mid=(start+end)/2;
        merge_sort(A,start,mid);
        merge_sort(A,mid+1,end);
        merge(A,start,mid,end);
    }
}

int main() {
    int size,i,*array;
    printf("Hello, World!\n");
    scanf("%d",&size);
    array=malloc(sizeof(int)*(size+1));
    for(i=1;i<=size;i++){
        scanf("%d",&array[i]);
    }
    merge_sort(array,1,size);
    for(i=1;i<=size;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
    printf("See you then, World!\n");
    return 0;
}