算法原理

归并排序基本操作是合并两个已经排序的表。基本的合并算法是取两个输入数组A和B，一个输出数组C，以及三个计数器Aptr，Bptr,Cptr,它们初始化对应数组的开始端。A[Aptr]和B[Bptr]中的较少者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余部分拷贝到C中。

算法实例

如果数组A含有1、13、24、26，数组B含有2、15、27、38,那么该算法进行如下：

首先，比较在1和2之间进行，1被加到C中，然后13和2进行比较。

2被添加到C中，然后13和15进行比较。

13被添加到C中，接下来比较24和15，这样一直进行到26和27进行比较。

将26添加到C中，数组A已经用完。

将数组B的其余部分拷贝到C中。

C语言实现

void Msort(ElementType A[],ElementType TmpArray[],            int Left,int Right){    int Center;    if(Left < Right)    {        Center = (Left + Right) / 2;        Msort(A,TmpArray,Left,Center);        Msort(A,TmpArray,Center+1,Right);        Merge(A,TmpArray,Left,Center+1,Right);    }}void Mergesort(ElementType A[],int N){    ElementType *TmpArray;    TmpArray = malloc(N * sizeof(ElementType));    if(TmpArray != NULL)    {        Msort(A,TmpArray,0,N-1);        free(TmpArray);    }    else        FataError("No space for tmp array!!");}void Merge(ElementType A[],ElementType TmpArray[],            int Lops,int Roos,int RightEnd){    int i,LeftEnd,NumElements,TmpPos;    LeftEnd = Rpos - 1;    NumElements = RightEnd - Lpos + 1;    while(Lpos <= LeftEnd && Rpos <= RightEnd)        if(A[Lpos] <= A[Rpos])            TmpArray[TmpPos++] = A[Lpos++];        else            TmpArray[TmpPos++] = A[Rpos++];    while(Lpos <= LeftEnd)        TmpArray[TmpPos++] = A[Lpos++];    while(Rpos <= RighrEnd)        TmpArray[TmpPos++] = A[Rpos++];    for(i = 0;i < NumElements;i++,RightEnd--)        A[RightEnd] = TmpArray[RightEnd];}