内部排序之---归并排序

【算法思想】
1：分治算法
分治模式在每一层递归上都有三个步骤。
（1）分解：将原问题分解成一系列子问题。
（2）解决：递归的解决各个子问题，若子问题足够小，直接求解。
（3）合并：将自问体结果合并成原文体的解。
2：合并排序
合并排序的三个步骤
（1）分解：将n个元素分成各含有n/2个元素的自序列
（2）解决：用合并排序算法对两个子序列递归排序
（3）合并：合并两个已经排序的子序列得到结果
3：归并排序
基本思想基于合并，将两个或者两个以上有序表合成一个新的有序表。
       假设有初始序列含有n个记录，首先将这n个记录堪称n个有序的子序列，每个自序列的长度为1，然后两两归并，得到[n/2]个长度为2的自序列
       在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序序列，依次重复。
【过程】
A（19   13）   (5   27  )               (1    26)    (31    16)
B（13    19） （5   27）             （1   26） （16   31）
C（5      13      19     27）            （1   16      26     31）
D（1       5      13       16         19      26      27      31 ）
归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。 

【算法描述】

void merge_sort(int *r,int low,int high,int *r2,int len)
{
    int i,j,k;
    int mid=(high+low)/2;
    i=low;
    j=mid+1;
    k=low;
    while(i<=mid&&j<=high)
    {
        if(r[i]<r[j])
        {
            r2[k]=r[i];
            ++i;
        }
        else
        {
            r2[k]=r[j];
            ++j;
        }
        ++k;
    }
    while(i<=mid)
    {
        r2[k]=r[i];
        ++i;
        ++k;
    }
    while(j<=high)
    {
        r2[k]=r[j];
        ++j;
        ++k;
    }
}
void Msort(int r[],int low,int high,int r3[],int len)
{
    int r2[len],mid;
    if(low==high)
        r3[low]=r[low];
    else
    {
        mid=(low+high)/2;
        Msort(r,low,mid,r2,len);
        Msort(r,mid+1,high,r2,len);
        merge_sort(r2,low,high,r3,len);
    }

}

【算法分析】
归并排序中总的时间复杂度是O（nlog2n）,空间复杂度为O(n)
【归并列子】

#include
#include
#include

void merge_sort(int *r,int low,int high,int *r2,int len)
{
int i,j,k;
int mid=(high+low)/2;
i=low;
j=mid+1;
k=low;
while(i<=mid&&j<=high)
{
if(r[i]
{
r2[k]=r[i];
++i;
}
else
{
r2[k]=r[j];
++j;
}
++k;
}
while(i<=mid)
{
r2[k]=r[i];
++i;
++k;
}
while(j<=high)
{
r2[k]=r[j];
++j;
++k;
}
}
void Msort(int r[],int low,int high,int r3[],int len)
{
int r2[len],mid;
if(low==high)
r3[low]=r[low];
else
{
mid=(low+high)/2;
Msort(r,low,mid,r2,len);
Msort(r,mid+1,high,r2,len);
merge_sort(r2,low,high,r3,len);
}

}
int main()
{
int i;
int r[]={1,4,3,9,7,12,8,5};
int len=8;
int	low=0;
int	high=len-1;
int r3[len];
Msort(r,low,high,r3,len);
for(i=0;i
printf("%d ",r3[i]);
printf("\n");
}