归并排序首先将数组分割为两组，然后递归排序左边，然后递归排序右边，然后将两个有序的数组进行归并为一个有序数组

如何保证分开的两组为有序数组呢？在不断的递归之下，我们最终会一定到达只有单元素的短链，左半边只有一个数字，右半边也只有一个数字，那么一定可以得到一个两位数的有序短链，循环往上，就可以得到整体的有序

C++

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 k = 0, i = l, j = mid + 1;//k为辅助数组的下标，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 (i = l, j = 0; i <= r; i ++, j ++ ) {
       q[i] = tmp[j];
    }
}