分治（归并排序）

一、基本思路

我们以一个归并排序为例。

. - 力扣（LeetCode）

归并排序的思想：得到两个有序数组，把两个有序数组合并，传到下一层递归，一直得到两个有序数组，一直合并，最后就能得到有序数组。

那其实有许多问题需要解释：

1、如何得到两个有序数组，一开始可都是乱序啊

一个数组一直被一分为二，最后是不是就会被分成一个数组里面就一个元素？一个元素不就有序了。

那么一旦我们有了两个有序数组，合并两个有序数组之后的大有序数组随递归传到上一层是不是就作为了一个有序数组，和另外一层递归上来的有序数组就可以再次合并，直到递归结束，数组就被排序完成了。

2、如何理解在函数最开始写上“mergeSort(left, mid, nums); mergeSort(mid + 1, right, nums);” 就可以认为接下来是排好序的两个有序数组呢？

因为在这两个语句之前所有的递归都是在做mergeSort(left, mid, nums); mergeSort(mid + 1, right, nums);这两个语句的左右数组排序，传递到这一层的递归就是左右有序的两个数组。

所以我认为的归并排序本质：就是把一个数组在中间劈开，然后交给下一层递归，一直把一段数组一分为二，直到一个数组里面只有一个，这时满足两个数组有序，开始回溯，合并两个有序数组后向上交付数组。

二、例题

1、逆序对

. - 力扣（LeetCode）

思路：我们得到一个数组，以mid为中心，在左边挑一下逆序对个数（不就是把左边看成一个数组，得到递归的结果），在右边挑一下逆序对个数，最后得到两个有序数组之后用一下两种方式调一下左右数组里面的逆序对。

但是上面代码中我递增归并一开始写成了 ans += cur2 - mid - 1，其实这是错的，错因是我在要cur2移动的情况下用右边的数组来统计逆序对个数是错的，因为没有判断左边的情况，所以这种题如果移动cur1就要以右边数组作为基准，移动cur2要以左边数组作为基准。

2、翻转对

. - 力扣（LeetCode）

思路：和上一题非常类似，但是注意由于不是1：1的关系，不能把计算结果的过程和排序混在一起，必须先是计算结果，再排序。

3、计算右侧小的元素个数

. - 力扣（LeetCode）

思路：和逆序对思路一样，只不过要注意由于是返回数组，我们必须记录原来数组中的值与下标的对应关系，但是请注意不能用哈希表记录，因为原数组会有重复，导致键值重复，所以只能用index数组对应值，值移动，index数组也移动。