Merge 将两个序列归并， MergePass 定义了在每一个长度下对序列怎样分区归并， MergeSort 以递增长度调用 MergePass

归并排序算法

void Merge(SqList R[],int low,int mid,int high) {
    SqList *R1;
    int i=low,j=mid+1,k=0;
    R1=(SqList *)malloc((high-low+1)*sizeof(SqList));
    while(i<=mid && j<=high) {
        if(R[i].key<=R[j].key) {
            R1[k]=R[i];
            i++;
            k++;
        } else {
            R1[k]=R[j];
            j++;
            k++;
        }
    }
    while(i<=mid) {
        R1[k]=R[i];
        i++;
        k++;
    }
    while(j<=high) {
        R1[k]=R[j];
        j++;
        k++;
    }
    for(k=0,i=low; i<=high; k++,i++)
        R[i]=R1[k];
}
void MergePass(SqList R[],int length,int n) {
    int i;
    for(i=0; i+2*length-1<n; i=i+2*length)
        Merge(R,i,i+length-1,i+2*length-1);
    if(i+length-1<n)
        Merge(R,i,i+length-1,n-1);
}
void MergeSort(SqList R[],int n) {
    int length;
    for(length=1; length<n; length=2*length)
        MergePass(R,length,n);
}