归并排序算法

算法思想：假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两合并，得到[n/2]个长度为2(n为奇数时，最后一个序列的长度为1)的有序子序列。

在此基础上再对长度为2的有序子序列进行两两合并，得到若干个长度为4的有序子序列。

如此重复，直到得到一个长度为n的有序子序列。

测试代码如下所示：

#include<stdio.h>
void Merge(int a[],int low,int mid,int high,int a3[])
{
    int i=low,j=mid+1,k=low;
    while((i<=mid)&&(j<=high))
    {
        if(a[i]<=a[j])
        {
            a3[k]=a[i];
            i++;

        }
        else
        {
            a3[k]=a[j];
            j++;

        }
        k++;

    }
    while(i<=mid)
    {
        a3[k]=a[i];
        k++;

        i++;

    }
    while(j<=high)
    {
        a3[k]=a[j];
        j++;
        k++;

    }
}
void MSort(int a[],int low,int high,int a1[])
{
    int a2[100];//辅助空间
    int mid;
    if(low==high) a1[low]=a[low];
    else
    {
        mid=(low+high)/2;
        MSort(a,low,mid,a2);//将数组a[]中的前半段的记录用归并法排序后放入a2[]数组的前半段
        MSort(a,mid+1,high,a2);//将数组a[]中的后半段的记录用归并法排序后放入a2[]的后半段
        Merge(a2,low,mid,high,a1);//将a2[]的前半段和后半段利用归并排序放入到a1[]数组中
    }

}
void main()
{
    int a[100];
    int a1[100];
    int length;
    int i;
    scanf("%d",&length);
    for(i=1;i<=length;i++)
        scanf("%d",&a[i]);
    MSort(a,1,length,a1);
    for(i=1;i<=length;i++)
        printf("%3d",a1[i]);
    printf("\n");
}

虽然说快速排序，堆排序比归并排序要简单一点儿，但是快速排序及堆排序都是不稳定的排序，而归并排序是稳定的排序算法。快速排序、堆排序和归并排序的平均时间复杂度均为(nlogn),但实验结果表明，就平均

时间性能而言，快速排序是所有排序算法中最好的，可是遗憾的是，快速排序在最坏情况下的时间性能为

O(n^2),而堆排序和归并排序的最坏时间性能仍为(nlogn),当n较大时，归并排序的性能优于堆排序，但它所需要的辅助空间最多。