《C++从入门到入土》——归 并 排 序

C++说要有顺序，于是便诞生了众多的排序算法。

众多排序算法中有一个玄学算法——归并排序。

归并排序有两个步骤——先分而治之。归并算法的核心是分治，顾名思义，分，就是把问题简化，分割成一个个容易计算的小问题；治，则是把求得子问题的所有答案汇总成整个问题的最终答案（为毛让我想起了动归？）。

首先，我们需要通过递归和二分的方法，将需要排序的原数组分割成多个临时数组。每个临时数组都是（在该次递归中的）原数组的一半长度，直至分割成无法再次分割的最小单位（在归并排序中就是数组中只有一个数，n=1）， 这部分的时间复杂度是log2n；

接着是“并”，也通过递归来实现，将每两个已有序的临时数组 合并成一个有序的临时数组（对于每个临时数组的区间来说都是有序的），将这部分有序的数还原到原数组中，最终将所有子数组合并成有序的原数组，这部分的时间复杂度是n（每个数扫一遍）。

最终的时间复杂度就是n*log2n。

详细的见代码描述。

有疑问评论区欢迎留言。

练习完的可以去洛谷P1177快速排序 提交（https://www.luogu.com.cn/problem/P1177），所有的排序题目都可以在上面提交。

如果觉得太简单的可以尝试洛谷P1908逆序对（https://www.luogu.com.cn/problem/P1908），虽然不是排序，但需要用到归并排序的思想（分治yyds）。

最后，老师的任务已经完成了，祝愿我原神胡桃二十抽直接出金！

QwQ Orz QaQ