七大排序之归并排序

<MergeSort>
效率分析：设数列长为N，将数列分开成小数列一共要logn步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(n)，故一共为O(nlogn)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(nlogn)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

/*秩都从0开始*/
void MergeSort(int *A,int lo,int hi)
{
    if(hi-lo<1) return;//区间内只有一个元素，必然有序
    int mi=(lo+hi)/2;//以中点为界
    MergeSort(A,lo,mi);//对前半段排序
    MergeSort(A,mi+1,hi);//对后半段排序
    Merge(A,lo,mi,hi);//归并
}

void Merge(int A[],int lo,int mi,int hi)
{
    int lb=mi-lo+1;
    int lc=hi-mi;

    int *B=new int[lb];   //为前子序列分配空间
    for(int i=0;i<lb;i++)  //把A中元素复制到B
        B[i]=A[lo+i];
    int *C=A+mi+1;   //C直接利用A的空间

    for(int i=lo,j=0,k=0;j<lb || k<lc;){
        if ( ( j < lb ) && ( ! ( k < lc ) || ( B[j] <= C[k] ) ) ) A[i++] = B[j++];
//利用||的短路特性，既保证了k未越界，同时比较了B、C元素
        if ( ( k < lc ) && ( ! ( j < lb ) || ( C[k] <  B[j] ) ) ) A[i++] = C[k++];
    }
    delete []B;
}