二分归并排序（分治法）

int *Merge(int *a, int f, int m, int e)//将两个排好的合到一起
{
    int *b = new int[e - f + 1];
    int flag1 = f, flag2 = m + 1;
    for(int i = 0; i <= e - f; ++i){
        if(flag1 > m)
            b[i] = a[flag2++];
        else if(flag2 > e)
            b[i] = a[flag1++];
        else if(a[flag1] >= a[flag2])
            b[i] = a[flag2++];
        else if(a[flag1] < a[flag2])
            b[i] = a[flag1++];
    }
    for(int j = f, k = 0; j <= e; ++j)
        a[j] = b[k++];
    delete [] b;
    return a;
}
int *Merge_sort(int *a, int f, int e)
{
    if(e > f){
        int m = (e + f) / 2;
        Merge_sort(a, m + 1, e);
        Merge_sort(a, f, m);
        Merge(a, f, m, e);
    }
    return a;
}

原理参见 屈婉玲老师 算法设计与分析 ORZ