记忆归并排序

其实代码就两个部分，前半部分是分治递归，后半部分是重新合并

归并就是先把数据按照左右区间逐个一分为二，所有的数都分开了，就是说每一个数
都被分成独立一个了。然后对每个左右区间合并，合并过程就是比较左右区间的谁小
谁就先放到下一级区间，然后如果左或者右区间先取完了，那只接把另一个剩下的所
有的数全加在下一级区间里面。

那么注意是需要两个数组，一个是 原视数组即结果，这里是q[]，一个是临时记录并归操作，这里是tmp[]
的阶段性排序的结果区间

左右区间我们不会额外用两个数组分别存储，只是在一个数组中用左右指针来划分左右

注意临时数组q[]必须是引用传输(用到&)，或者是全局变量，而tmp值传输,引用传输，是否全局似乎都行，无影响

q[]总是用l，r这两个指针作为下标

//左右两个双指针，和一个原始数组q[](即结果),tmp是函数里面用的辅助数组
void merge_sort(int q[], int l, int r)
{
    //左指针不能大于或者等于右指针
    if (l >= r) return;
    //确定开始分治的下标
    int mid = l + r >> 1;
    //一个往左一个往右开始递归，也简称为分治递归
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    //开始合并



    //第一种
    int tmp[N];
    int k=0,i=l,j=mid+1;
    //i遍历左区间，j遍历右区间，比较谁小谁就先存入临时数组里面
    while(i<=mid && j<=r){
        if(q[i]<q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    //当某个区间遍历完了，就把另一个区间的剩下的所有值直接依次放在临时数组里面
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    //最后把对应上面处理到的区间的临时数组放到全局数组对应的位置上就行了
    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];



    //第二种
    vector<int> tmp;
    int i = l, j = mid + 1;
    //i遍历左区间，j遍历右区间，比较谁小谁就先存入临时数组里面
    while (i <= mid && j <= r)
    if (q[i] <= q[j]) tmp.push_back(q[i ++ ]);
    else tmp.push_back(q[j ++ ]),res += mid - i + 1;;
    //当某个区间遍历完了，就把另一个区间的剩下的所有值直接依次放在临时数组里面
    while (i <= mid) tmp.push_back(q[i ++ ]);
    while (j <= r) tmp.push_back(q[j ++ ]);
    //最后把对应上面处理到的区间的临时数组放到全局数组对应的位置上就行了
    int k=l;
    for (auto x : tmp) q[k ++ ] = x;

    似乎只能是tmp是vector时，才可以foreach给q，不然会出错
}


归并排序
我们需要三个变量，一个数组(全局或者引用传递)，一个左边界下标，一个右边界下标
1.先把区间分为左右区间，分别递归
2.建一个临时数组，比较左右区间，从小到大填入到临时数组中去
3.把临时数组全部赋给开始的变量数组(临时数组是vector才能用foreach赋值)