1. 归并排序是将两个有序表合并成一个新的有序表，把待排序的数组分解成子序列，对子序列排序然后合并，归并排序使用了递归和分治的方法。合并两个有序数组A和B，采用循环遍历的方法，定义两个变量i,j，分别指向A和B的起始端，依次比较对应元素大小，选择较小的放入数组C，然后将对应的变量i或者j加1.
合并数组的代码是（合并a数组中left至mid,mid+1到right的元素）：
void merge(int a[],int temp[],int left,int mid,int right)
{
int i=left,j=mid,k=0;
while(i<mid&&j<=right)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<mid)
temp[k++]=a[i++];
while(j<=right)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[left+i]=temp[i];
}
归并排序用到分治算法，下面是归并排序的主函数：
void mergesort(int a[],int tmp[],int left,int right)
{
if(left<right)
{
int mid=(left+right)/2;
mergesort(a,tmp,left,mid);
mergesort(a,tmp,mid+1,right);
merge(a,tmp,left,mid+1,right);
}
}
2.假设有数组a[10]={2,34,13,87,47,52,19,4},归并排序的过程是
第一趟：(2,34),(13,87),(47,52),(4,19)
第二趟：(2,13,34,87),(4,19,47,52)
第三趟：(2,4,13,19,34,47,52,87)
3.完整的归并排序代码为：
# include <iostream>
using namespace std;
# include <stdlib.h>
int main()
{
void fsort(int a[],int n);
int i;
int a[10]={2,34,13,87,47,52,19,4,79,35};
fsort(a,10);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
system("pause");
return 0;
}
void merge(int a[],int temp[],int left,int mid,int right) //合并两个数组
{
int i=left,j=mid,k=0;
while(i<mid&&j<=right)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<mid)
temp[k++]=a[i++];
while(j<=right)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[left+i]=temp[i];
}
void mergesort(int a[],int tmp[],int left,int right) //合并排序
{
if(left<right)
{
int mid=(left+right)/2;
mergesort(a,tmp,left,mid);
mergesort(a,tmp,mid+1,right);
merge(a,tmp,left,mid+1,right);
}
}
void fsort(int a[],int n)
{
int *tmp=(int *)malloc(n*sizeof(int));
mergesort(a,tmp,0,n-1);
free(tmp);
}
4.归并排序分析
归并排序采用分治算法，采用二分法时，时间复杂度是O(lgn),两个数组合并，时间复杂度是O(n),归并排序的时间复杂度是O(n*lgn)。
归并排序是稳定的排序算法，这是它由于快速排序的地方，但是它需要额外的空间来存放数组元素，在待排序元素数量很多，需要在主存中排序，在内存小的机器中，计算机内存需要主存中读取和存储元素，此时归并排序消耗的时间会远远大于快速排序。
原文：http://blog.csdn.net/u011608357/article/details/21331529