C++ 二路归并排序-递归实现

核心思想:先递归划分，然后合并的时候相当于合并两个有序数组，需要用到一个额外数组，最后把额外数组的元素依次赋给原数组，注意函数参数为引用

//统一接口
    void Merge_sort(vector<int> &num, int n){
        vector<int> temp(n);
        Msort(num, temp, 0, n-1);

    }
    
    //递归划分
    void Msort(vector<int> &num, vector<int> temp, int l, int rightend){
        int center;
        if(l < rightend){
            center = l + (rightend - l) / 2;
            Msort(num, temp, l, center);
            Msort(num, temp, center+1, rightend);
            Merge(num, temp, l, center+1, rightend);
        }

    }
    
    //合并,相当于两个有序数组并列在一排第一个数组从l开始，到r-1结束，第二个数组从r开始，到rightend结束
    void Merge(vector<int> &num, vector<int> temp, int l, int r, int rightend){
        int leftend = r - 1;
        int index = l;//存放数组Temp初始位置
        int n = rightend - l + 1;//数组长度
        while(l <= leftend && r <= rightend){
            if(num[l] <= num[r]) temp[index++] = num[l++];
            else  temp[index++] = num[r++];
        }
        while(l <= leftend)
            temp[index++] = num[l++];
        while(r <= rightend)
            temp[index++] = num[r++];
        for(int i = 0; i < n; ++i, --rightend)
            num[rightend] = temp[rightend];
    }