归并排序模板

模板在文末，以下步骤方便理解记忆。

先贴一张快速排序模板步骤，用于对比记忆

归并排序步骤：

（0）如果数组左边界L ≥ 数组右边界，则不需要排序，直接return。

（1）直接取数组正中间的数，即 mid = (L+R) / 2为边界。

（2）先递归，对 L~mid ，mid+1 ~ R 这两个区间的数组调用归并排序函数。

（3）对于每次归并，它的面前有两个排好序的数组，即 [ L, mid ] 和 [ mid+1, R ]，接下来需要把这两个数组合为另一个有序的数组。

具体操作是采用双下标指针，首先令 i = L，j = mid + 1（即两个数组的左边界）

接着，让q[ i ]和q[ j ]中更小的那个先放进 temp 数组里，然后 i++ 或 j++，以此类推。

当其中一个下标指针到达末端时，直接将另一个数组原封不动的拷贝进 temp 数组里。

（4）最后把 temp 数组拷贝到 q 数组中。（这一步容易写错）

#include<iostream>
using namespace std;

const int N = 100010;

int n;
int q[N], temp[N];

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 i = l, j = mid+1, k = 0;
    while(i <= mid && j <= r) //对应步骤(3),而且当两个数组的指针都没有越界时才这么做
    {
        if(q[i] < q[j]) temp[k++] = q[i++];
        else            temp[k++] = q[j++];
    }
    while(i <= mid)     temp[k++] = q[i++]; //如果i没有越界,则将i后面的原封不动地拷贝进去
    while(j <= r)       temp[k++] = q[j++]; //如果j没有越界,则将j后面拷贝进去
    
    //q和temp数组的范围不同，因此需要两个变量i,j
    //         注意不是i <= n
    for(int i=l, j=0; i <= r; ++i, ++j) q[i] = temp[j]; //步骤(4),注意写法
}

int main()
{
    scanf("%d", &n);
    
    for(int i=0;i<n;++i) scanf("%d", &q[i]);
    
    merge_sort(q, 0, n-1);
    
    for(int i=0;i<n;++i) printf("%d ", q[i]);
    
    return 0;
}