算法基础——归并排序

分治法的思想是将原问题分解为几个规模小的同类问题，递归地求解这些子问题，然后再将子问题的解合并去解决原问题。
分治法每层递归可以分为三个步骤：
1.分解：将大的问题分解成同类型的小问题
2.解决：递归解决各个子问题，直到当前子问题无法继续分割或者小于某个规模
3.合并：将分割后的子问题的解依次合并，组成原问题的解
书上举的例子的归并排序，并且将归并排序的过程用文字描述了出来：
分解：将待排序的n个元素的序列分解成各具n/2个元素的两个子序列
解决：使用归并排序递归地将排序两个子序列
合并：合并两个已经排序的子序列以产生已排序的答案
下面是书中给出的伪代码：

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1+1] and R[1...n2+1] be new arrays
    for i = 1 to n1
        L[i] = A[p+i-1]
    for j = 1 to n2
        R[j] = A[q+j]
    L[n1+1] = ∞
    R[n2+1] = ∞
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

MERGE-SORT(A, p, r)
    if p < r
        q = ⌊(p+r)/2⌋
        MERGE-SORT(A,p,q)
        MERGE-SORT(A,q+1,r)
        MERGE(A,p,q,r)

解释一下上面的伪代码中的一些细节，L[n1+1]和R[n2+1]＝∞是为了在当前位置终止，不再继续往后进行比较防止数组越界；MERGE-SORT中先调用两个SORT函数后调用MERGE函数是为了保证前后数组各自是有序的，才能保证合并后的数组是有序的当子数组长度为1时必定有序，所以可以进行合并。
将代码换成注释重新填写一遍：

void merge(---){//传入相关参数（数组，起始坐标）
    //定义变量表示中间值左右数的数量，定义数组并存放排好序的子数组
    //将定义的数组以大于数组极大值结尾防止数组越界
    //定义两个指针对数组对应位置的数进行比较，将大的（小的）存放进原数组
}

void merge_sort(---){//传入相关参数（数组，起始坐标）
    //当长度大于1时将数组分成两份，分别对两份子数组进行排序（递归操作），然后再将两个数组合并
}

最后将注释部分补全，这里用c++举例子：

void merge(int* A, int p, int q, int r){
    /*
        A:要进行合并的数组
        p:第一个子数组的起点
        q:第二个子数组的起点
        r:第二个子数组的终点
    */
    int n1 = q - p;
    int n2 = r - q;
    int L[100], R[100];
    for(int i = 0; i < n1; i++) L[i] = A[p + i];
    for(int i = 0; i < n2; i++) R[i] = A[q + i];
    L[n1] = 1e9+7;
    R[n2] = 1e9+7;
    int i = 0, j = 0;
    for(int k = p; k < r; k++){
        if(L[i] <= R[j]) A[k] = L[i++];
        else A[k] = R[j++];
    }
}

void merge_sort(int* A, int p, int r){
    /*
        A:要进行排序的数组
        p:数组要排序的部分的起点
        r:数组要排序的部分的终点
    */
    if(p < r-1){
        int q = (p+r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q, r);
        merge(A, p, q, r);
    }
}