引言

归并排序是什么？是建立在归并操作上的一种有效，稳定的排序算法。🙃不明觉厉~

最差的时间复杂度也有O(nlogn)。牛~

归并排序跟二分，快速排序一样，也是分治算法。

三步走

（1）分解成可解的子问题
（2）求解子问题
（3）合并子问题的解并构成原问题的解。

归并排序的粗略概括

将一段序列不断的迭代划分成两个区间，直到子区间为空或者只剩一个元素。

那么也就意味着所有子区间都成了有序的序列。

（没有元素和一个元素算作序列有序）

然后不断将已有序的子序列递归合并，最终得到完全有序的序列；

聪明的小伙伴立马注意到加粗的字体。good~

迭代划分成两个区间? （1）分解成可解的子问题
直到子区间为空或者只剩一个元素 递归边界终止的条件
将已有序的子序列递归合并（3）合并子问题的解并构成原问题的解。

分治步骤的（2）求解子问题 哪去了？ 被吃掉了吗？giao!

实际上，求解子问题隐含在了（1）（3）之中。

（1）子区间为空或者只剩一个元素，已经自动有序了。
（3）合并的时候，双指针排序，也把子问题给解决了。

漂亮~

归并排序双指针模板

int q[N],tmp[N];//归并排序需要额外的空间来辅助
void merge_sort(int q[], int l, int r)
{
    //递归边界的终止条件
    if(l >= r) return;//直到子区间为空或者只剩一个元素
    //第一步：分成子问题
    int mid = l + r >> 1;//当只有两个值时，mid = l 不会出现无限划分死循环。
    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);
    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1;//k指向temp, i 指向第一段子区间，j指向第二段子区间。
    while(i <= mid && j <= r)//i和j都没指到终点。
        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, k = 0; i <= r; i ++, k ++ ) q[i] = tmp[k];//记得把tmp存储的放回q[l..r]中
}

总结

1.找到mid,[l..r] => [l..mid] + [mid + 1, r]。
2.递归排序[l..mid] 和 [mid + 1, r]。
3.归并，将两个有序序列合并成一个有序序列。扫尾+物归原主。