Merge sort

分治：与quick sort不同，merge sort从中间排序。以中间点为界限。
时间复杂度是Θ(nlgn)。

1：确定分界点：mid (下标的中间值：(l + r)/2)。
2：递归排序左边与右边。
3：归并（merge）两个有序的数组合并成一个有序的数组, O(n)。
通过双指针算法实现（双路归并）：
假设两个有序的序列，指针分别指向数组的开头位置。
第一个指针指向第一个数组的最小值，第二个指针指向第二个数组的最小值。不断比较两个指针指向的数字，将较小值放入新的数组中，并向后移动对应指针。如果相同，先移动第一个数组的指针，确保排序算法稳定（原序列中如果数字相同，相对位置是不变的。快排是不稳定的，归并是稳定的）。

模板代码：

const int N = 1000010;
int n; 
int q[N], tmp[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);
//归并数组，合二为一
//归并排序比快排需要使用一个额外的数组tmp
//k记录已经合并的元素个数，指针i与j
    int k = 0, i = l, j = mid + 1;
    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 ++ ];
//将结果复制回原数组q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}