归并排序

1. 迭代和递归
2. 整数的最大值20多亿，溢出会变成负数

小和问题

一个组内部不产生小和===>因为之前已经产生过了
不同组之间会产生小和
其实是有小和产生的，只不过只有0个数比该数大，此时0*该数为0，不用加
大于号取不取等于号对稳定性有影响

逆序对数

从右向左merge（升序 ）
也可以排成降序从左开始
不回退的技巧（左右组都是有序的必然不回退）===>分组！来源于单调性（有单调性一般和不回退联系在一起或者二分）
将要做的处理处理完了之后再单独去合并merge===>合并前先计算值
单独拎出来，写在一起太杂
O(N)+O(N)还是O(N)
编程技巧：windowR是到不了的位置，是从[M+1, windowR)左闭右开，开始一个数也没有

一个for循环八条语句和两个for循环各四条语句，选后者，因为8条的思维很乱；复杂度一样，何必为难自己
将复杂的逻辑拆分开！

本质是mergeSort将数据变为有序的东西，这个有序的东西可以用来求很多东西

大于右边的两倍

得手写代码，面试时得再白纸上写

开始学的时候可以背思路

当你想求右边整体个数的时候或者怎么样的时候，都往mergeSort上靠，这就是归纳题型

讲的是原型，需要会变换