数组划分为单一元素的子数组，这些子数组显然是有序的。
每两个子数组合并成一个数组，直至合并为原来的数组大小

/* *********************************************************************
 *                         归并排序
 * *********************************************************************/


/* *********************************************************************
 * function     : merge
 * description  : 合并两个已排好序的数组
 * input        : int A[],int p,int q,int r
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-18
 * **********************************************************************/

void merge(int A[], int p, int q,int r){
    int n1 = q - p +1;
    int n2 = r - q;
    int L[n1+1];
    int R[n2+1];
    for (int i = 0; i < n1; ++i) {
        L[i] = A[p+i];
    }

    for (int j = 0; j < n2; ++j) {
        R[j] = A[q+1+j];
    }

//    哨兵，可以不用检查数组是不是为空
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;

    int i = 0;
    int j = 0;
    for (int k = p; k <= r; ++k) {
        if (L[i]<=R[j]) {
            A[k] = L[i];
            i++;
        } else{
            A[k] = R[j];
            j++;
        }
    }
}

/* **********************************************************************
 * function     : mergeSort
 * description  : 将待排序数组分解为两个子数组，分别对两个子数组递归调用mergeSort()
 * input        : int A[],int p,int r
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-19
 * **********************************************************************/
void mergeSort(int A[], int p,int r){
    if (p<r){
        int q = (p+r)>>1;
        mergeSort(A,p,q);
        mergeSort(A,q+1,r);
        merge(A,p,q,r);
    }
}



void initARandom(int A[],int length){
    srand(time(0));
    for (int i = 0; i < length; ++i) {
        A[i] = rand()%60;
    }
}

int main(int argc, char const *argv[])
{
    int length = 12;
    int A[length];
    /* *****************************************
     * 归并排序测试
     * *****************************************/

    initARandom(A,length);
    print_array(A,length,"before merge sort:");
    mergeSort(A,0,length-1);
    print_array(A,length,"after merge sort");

    return 0;
}