归并排序

〇、返回

一、概述

归并排序和快速排序是最常用的两种排序方式，以 O(n log n)$ 的时间复杂度拉爆其它基于比较的排序喵

在STL里也有对这两种排序的封装：stable_sort() 是归并排序的封装函数，sort()是快排+归并多种排序综合的封装，相对来讲更快，也是最常用的

归并排序是以划分子问题（分治）为中心思想的排序算法，具有稳定、复杂度低等优点，还可以同时实现统计逆序对（划重点），但实现上空间开销比较大，常数略高，因此相比快排用的少一些

二、算法步骤

1.递归 将当前区间分成两个部分并递归下去，直到区间中只有一个元素（相当于有序了）

2.合并 此时获得了两个有序区间。遍历两个区间，两个指针分别指向两个区间中的最小(大)值，将更小(大的一个放进辅助数组中并往后跳一个，合并完后将辅助数组中的内容再填回区间中即可；

统计逆序对也在合并这一步骤中完成：

注意到每一次放入辅助数组中的数都是两个区间所有数中最小的一个，因此当右侧区间有数被放入辅助数组中时，意味着左侧区间剩余的所有数都大于这个数，且位置更靠前(这个显然)，亦即都会与这个数构成逆序对，统计即可。

三、时空复杂度

时间复杂度：$O(n log n)$；

空间复杂度：$O(n)$，合并时的辅助数组

因为有递归和较多的遍历操作，实现时常数偏大，跑大数据会比较危险

四、代码

等我驯服ai审核后再搞文字版出来

重在理解喵

刚刚发现一个问题但懒得改了) 在这说一嘴

函数返回前或者在合并前要把 tp 归零，不然会炸的

致歉TT