归并排序：的时间复杂度是o（nlgn）。
归并排序的步骤是：
divide：把长度为n的输入序列分成两个长度为n/2的子序列。
conquer：对这两个子序列分别采用归并排序
combine：将两个排序好的子序列合并成最终的排序序列，
在描述归并排序的步骤的时候，我们有调用归并排序本身，可见这是一个递归的过程。（栈模式）
下面是一个归并排序的例子：
#include<stdio.h>
#define LEN 8
int a[LEN]={5,2,4,7,1,3,2,6};
void merg(int start,int middle,int end)
{
int n1=middle-start+1;
int n2=end-middle;
int left[n1],right[n2];/*c99的新特性，可变长数组*/
int i,j ,k;
for(i=0;i<n1;i++)
left[i]=a[start+i];/*将数组元素放入left数组，放入，N1个元素*/
for(j=0;j<n2;j++)
right[j]=a[middle+1+j];/*the same with left*/
i=j=0;
k=start;
while(i<n1&&j<n2)
if(left[i]<right[j])
a[k++]=left[i++];
else
a[k++]=right[j++];
while(i<n1)
a[k++]=left[i++];
while(j<n2)
a[k++]=right[j++];/*把剩下的元素放在排序中*/
}
void sort(int start,int end)
{
int mid,i;
if(start<end)
{
mid=(start+end)/2;
sort(start,mid);
sort(mid+1,end);
merge(start,mid,end);
}
for(i=0;i<LEN;i++)
printf("%d ",a[i]);
}
int main(void)
{
sort(0,LEN-1);
return 0;
}
sort函数把数组分成两个子序列，然后在对这两个子序列分别调用sort函数来排序，最后调用merg函数来合并，合并的时候，每次循环取序列中最小的元素进行比较，将较小的元素取出放到最终的排序序列中，如果其中的一个子序列元素已经取完，就把列外的子序列的元素都放到排序序列中。
归并排序的时复杂度：
首先，我们有两个函数，对于merge函数，O（n），因为在循环中，循环一起看的话，每一次执行后都会排列好一个元素，有n个元素，故为O（n），
sort函数的时间复杂度：当输入n=1时，执行时间为常数，
当n》1时，总的时间为2*输入长度为n/2的sort函数的时间。
所以时间复杂度可以用这个表达式来表示：T(n)=O(1);if n=1
2*T(n/2)+O(n);if n>1
我们对其分解后，发现是T(N)可以分解成一个满二叉树的结构。
如下：
cn
T(n/2) T(n/2)
进一步分解为：
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
我们对于满二叉树计算它的高度：设深度为k，
有节点为n
k
则有：n=2 -1；
n
所以：k=lg -1
同时每一层的和都是cn，所以：总的执行时间可表示为：
n n
cnlg +cn，相比nlg，cn可以忽略不计。
n
所以有：归并排序的时间复杂度是：O(nlg );
显然比插入排序快。