merge sort

/*  MAXN为A的长度上限 
    inf 是一个大整数  
    数组计数从0开始  
*/

void merge(int A[],int p,int m,int q) {
    int i,j,k;
    int L[MAXN+1], R[MAXN+1];

    i = j = 0;
    for(k = p ; k <= m ; k ++)
    {
        L[i++] = A[k];
    }
    for(k = m+1 ; k <= q ; k ++)
    {
        R[j++] = A[k];
    }
    L[i] = R[j] = inf;

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

void merge_sort(int A[] , int p,int q) {
    if(q > p) {
        int m=(p+q)/2;
        merge_sort(A,p,m);
        merge_sort(A,m+1,q);
        merge(A,p,m,q);
    }
}