归并排序
两个有序数组的归并 数组 a 和数组 b 都是非降序的数组，数组长度分别为 m 和 n ，将两个数组合并成一个升序数组 c ，程序如下所示：
void merge(int * a,int m,int * b,int n,int * c)
{
int i,j,k;
i=j=k=0;
while(i<m && j<n)
{
if(a[i]<b[j])
{
c[k++]=a[i++];
}
else
{
c[k++]=b[j++]
}
}
while(i<m)
{
c[k++]=a[i++];
}
while(j<n)
{
c[k++]=b[j++];
}
}
将一个无序数组利用归并排序排列成一个升序数组，程序如下所示。首先递归调用 merge_sort 函数，直至将序列划分成两个单个元素组成的子序列，再调用 merge_array 将两个元素组成的子序列保持升序，再返回到上一层递归，调用 merge_array 将两组由两个元素构成的子序列排成四个元素的升序序列，依次递归，使得整个序列升序。
void merge_array(int * a,int first,int mid,int last,int * tem)
{
int i=first,m=mid,j=mid+1,n=last;
int k=first;
while(i<m && j<n)
{
if(a[i]<a[j])
{
tem[k++]=a[i++];
}
else
{
tem[k++]=a[j++];
}
}
while(i<m)
{
tem[k++]=a[i++];
}
while(j<n)
{
tem[k++]=a[j++];
}
for (int t = first; t <= last; t++)
{
a[t]=tem[t];
}
}
void merge_sort(int * a,int first,int last,int * tem)
{
if(first<last)
{
int mid=(last+first)/2;
merge_sort(a,first,mid,tem);
merge_sort(a,mid+1,last,tem);
merge_array(a,first,mid,last,tem);
}
}
