归并排序

归并排序是利用归并的思想对数列进行排序。--将两个有序数列合并成一个有序数列，称之为“归并”，归并包括从上往下和从下往上两种方式。

1. 从下往上的归并排序 :将待排序数组分成若干个长度为1的子数列，然后再将这些数列两两合并，得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并直到合并为一个数列为止，这样就得到最终结果。
2. 从上往下的归并排序 :它与从上往下的在排序方向上是相反的，包括三步：
   (1): 分解----将当前区间一分为二，即求分裂点mid=(low+high)/2;
   (2): 求解----递归的对两个子区间a[low...mid]和a[mid+1...high]进行归并排序，递归的终结条件是子区间的长度为1.
   (3):合并----将已经排好序的两个子区间a[low...mid]和a[mid+1...high]归并为一个有序的区间a[low...high].

归并排序的时间复杂度和稳定性

归并排序的时间复杂度是O(NlgN):归并排序的形式是一颗二叉树，他需要遍历的次数就是二叉树的深度。而根据完全二叉树可以得出他的时间复杂度是O(NlgN).

归并排序的稳定性

归并排序是稳定的算法

1.从上往下的归并排序

void Merge(int *a,int start,int mid,int end,int *tmp)
{
    int i=start;
    int j=mid+1;
    int k =0;
    while(i<=mid && j<=end)
    {
        if(a[i]<=a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i<=mid)
        tmp[k++] = a[i++];

    while(j<=end)
        tmp[k++] = a[j++];  

    for (i = 0; i<k; ++i)
        a[start+i] = tmp[i];
    return ;
}
void Merge_Step(int *a,int start,int end,int *tmp)
{
    if(start<end)
    {
        // int mid = (end+start)/2;
        // int mid = start+(end-start)/2;
                int mid = start+((end-start)>>1);
        //这里和上面是一样的但是可以解决end和start都很大的情况下，start+end溢出的情况
        Merge_Sort(a,start,mid,tmp);
        Merge_Sort(a,mid+1,end,tmp);
        Merge(a,start,mid,end,tmp);
    }
}

void Merge_Sort(int *a,int len)
{
    int i=0;
    int n=len-1;
    int *tmp = (int *)malloc(len*sizeof(int));
    Merge_Step(a,0,n,tmp);
    free(tmp);
}

２．从下往上的归并排序

void Merge(int *a,int start,int mid,int end,int *tmp)
{
    int i=start;
    int j=mid+1;
    int k =0;
    while(i<=mid && j<=end)
    {
        if(a[i]<=a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while(i<=mid)
        tmp[k++] = a[i++];

    while(j<=end)
        tmp[k++] = a[j++];  

    for (i = 0; i<k; ++i)
        a[start+i] = tmp[i];
    return ;
}
void Merge_step(int *a,int len,int step,int *tmp)
{
    int i =0;
    for (; i+2*step-1 < len; i+=2*step)
        Merge(a,i,i+step-1,i+2*step-1,tmp);

    if (i+step-1 < len-1)
        Merge(a,i,i+step-1,len-1,tmp);
}

int Merge_Sort(int *a,int len)
{
    assert(a);
    int *tmp = (int *)malloc(len*sizeof(int));
    if(NULL == tmp)
        return -1;

    int i=1;
    for (; i < len; i<<1)
        Merge_step(a,len,i,tmp);
    free(tmp);
}