//两个有序子序列合并成一个子序列
ElemType* B = (ElemType*)malloc((n + 1) * sizeof(ElemType));
void Merge(ElemType A[], int low, int mid, int high) {
    int i, j;
    for (int k = low; k <= high; k++)
        B[k] = A[k];
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (B[i] < B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while (i <= mid) A[k++]=B[i++];
    while (j <= high) A[k++] = B[j++];
}
//2-路归并排序的递归算法
void MSort(ElemType r1[], int low, int high, ElemType r3[]) {
    ElemType *r2;
    r2 = (ElemType*)malloc(sizeof(ElemType) * (high - low + 1));
    if (low == high)
        r3[low] = r1[low];
    else {
        mid = (low + high) / 2;
        MSort(r1, low, mid, r2);
        MSort(r1, mid + 1, high, r2);
        Merge(r2, low, mid, high, r3);
    }
    free(r2);
}
//2-路归并排序的初始调用过程
void MergeSort(ElemType A[], int n) {
    MSort(A, 1, n, A);
}