归并排序

归并排序是一种时间复杂度为O(NlogN)的排序算法，其和快速排序一样基于分治的思想，但又不完全相同。比起快速排序平均O(NlogN)的复杂度(最差退化成N^2),归并排序不会退化，是一种稳定的算法

对于无序数列a[N]在闭区间[L,R]的归并排序:

1. 找出数列中点mid
2. 递归访问由中点间断开的两个子序列
3. 将两个排序好的子序列填入[L,R]

也就是说，如果我们可以将原数列分成两个有序数列，我们就可以将这两个有序数列依次填入实现排序，从而我们可以把[L,R]的排序问题转化成[L,mid],[mid+1,R]两个子区间的排序，从而实现递归，递归的底层即区间长度为一

现在解决将两个有序数列合并成一个的问题，我们用双指针法，依次从头访问两个数列，比较两个元素的大小，填入小的一个，直到一个指针指向其数列的末尾，我们就将另一数列的剩余元素全部填入

完整代码如下

void merge_sort(int a[],int l,int r){
    if(l>=r)
        return ;
    int mid=(l+r)/2;

    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);

    //两个子序列分别是l~mid，mid+1~r
    int t=0,i=l,j=mid+1;//t用来往temp中装填，i，j是两个指针
    while(i<=mid && j<=r)//有一个指针到头就停止
        if(a[i]<=a[j])
            temp[++t]=a[i++];
        else
            temp[++t]=a[j++];
    //别忘了把没有到头的子序列剩余元素全部装填进temp
    while(i<=mid)    temp[++t]=a[i++];
    while(j<=r)  temp[++t]=a[j++];

    //将temp中排序好的元素依次装入a[]
    for(int i=l,j=1;i<=r;i++,j++)
        a[i]=temp[j];
}

现在讨论时间复杂度问题，对于第一次访问（第一层），我们会扫描整个数组，耗时为N。第二层时，分别扫描两个长度为\frac{N}{2}的数组，耗时依然为N，以此类推，每一层递归耗时都应为N。而递归层数不难得出是\log_{2}{N} 所以时间复杂度应该是O(N\log_{2}{N})