數(shù)組劃分為單一元素的子數(shù)組，這些子數(shù)組顯然是有序的星立。
每兩個子數(shù)組合并成一個數(shù)組，直至合并為原來的數(shù)組大小

/* *********************************************************************
 *                         歸并排序
 * *********************************************************************/


/* *********************************************************************
 * function     : merge
 * description  : 合并兩個已排好序的數(shù)組
 * 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];
    }

//    哨兵，可以不用檢查數(shù)組是不是為空
    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  : 將待排序數(shù)組分解為兩個子數(shù)組炒考，分別對兩個子數(shù)組遞歸調(diào)用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;
}