归并排序

归并排序分治法的一个典型且基本的应用。它的基本思想是：将对N个对象的问题转换成两次对N/2个对象的问题。归并排序减少了数据的比较次数，转而增加了数据的移动次数，使得排序速度相对较快。该算法的递推公式T(N) = 2T(N/2) + O(N)表明其算法复杂度上限为O(NlogN)。下面是其C++代码：

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int innersort(int* A,int left,int right,int* CPY)
{//[left,mid]and[mid+1,right];
    if(right==left)return 0;
    int mid=(left+right)/2;
    int i=left,k=mid+1;
    int cur=left;
    while(i!=mid+1&&k!=right+1)
    {
        if(A[i]>A[k])CPY[cur++]=A[k++];
        else CPY[cur++]=A[i++];
    }//一定有一侧的数据会最先完成排序
    while(i!=mid+1)CPY[cur++]=A[i++];
    while(k!=right+1)CPY[cur++]=A[k++];//对剩余的一侧数据一次添加进入CPY数组即可
    memcpy(A+left,CPY+left,sizeof(int)*(right-left+1));//复制回到原数组
    return 0;
}

int merger(int* A,int left,int right,int* CPY)
{//[left,mid]and[mid+1,right];
    if(left<right)
    {
        int center=(left+right)/2;
        //中点的归属需要特别考虑
        merger(A,left,center,CPY);
        merger(A,center+1,right,CPY);
        innersort(A,left,right,CPY);
    }
    return 0;
}

int mergesort(int* A,int* Aend)
{//[left,right);
    int right=Aend-A;
    int* temp=new int[right+1];//临时数组开得大了一点
    merger(A,0,right-1,temp);
    //数组的边界问题与分割方案问题一直是关注点
    delete[] temp;
    return 0;
}

int main()
{
    int aim[]={3,5,2,6,7,3,2,6,2,6,3,7,3,2};
    mergesort(aim,aim+14);
    for(int i=0;i<14;i++)
    {
        printf("%d ",aim[i]);
    }
    printf("\n");
    return 0;
}

归并排序中的比较次数是所有排序中最少的。原因是，它一开始是不断地划分，比较只发生在合并各个有序的子数组时。

因此，JAVA的泛型排序类库中实现的就是归并排序。因为：对于JAVA而言，比较两个对象的操作代价是很大的（根据Comparable接口的compareTo方法进行比较），而移动两个对象，其实质移动的是引用，代价比较小。（排序本质上是两种操作：比较操作和移动操作）

归并排序算法分析

 归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

它将数组平均分成两部分: center = (left + right)/2，当数组分得足够小时---数组中只有一个元素时，只有一个元素的数组自然而然地就可以视为是有序的，此时就可以进行合并操作了。因此，上面讲的合并两个有序的子数组，是从 只有一个元素 的两个子数组开始合并的。

合并后的元素个数：从 1-->2-->4-->8......

比如初始数组：[24,13,26,1,2,27,38,15]

①分成了两个大小相等的子数组：[24,13,26,1]    [2,27,38,15]

②再划分成了四个大小相等的子数组：[24,13]   [26,1]    [2,27]    [38,15]

③此时，left < right 还是成立，再分：[24]   [13]   [26]    [1]    [2]     [27]    [38]   [15]

此时，有8个小数组，每个数组都可以视为有序的数组了！！！，每个数组中的left == right，从递归中返回，故开始执行合并：

merge([24],[13]) 得到 [13,24]

merge([26],[1]) 得到[1,26]

.....

.....

最终得到 有序数组。