对于1和3来说 左侧指针指向1，右侧指针指向3
当左侧比右侧小的时候 1小于3 1的右侧有1个数比1大 所以产生1个1的小和
拷贝到外排序数组中
然后左侧就越界了
右侧的3也拷贝进来
将外排序数组中的1，3修改回原数组还是1，3
即在1～3范围上merge的时候 产生了1个1的小和
此时左侧的1，3和右侧的4分别已经排好序了 然后在一起merge
左侧指针指向1 右侧指针指向4
右侧是4 只有4这一个数比1大 所以此时产生1个1小和 拷贝到外排数组
移动左侧下标 指向3 右侧只有一个数大于3 产生1个3的小和
拷贝到数组
左侧再移动 就越界了 右侧的4拷贝下来
外排数组拷贝回原数组
2和5同理
2的右侧只有一个5大于2 所以产生了1个2的小和
将2放入排序数组
左侧指针再移动 越界
将5拷贝到外排数组
再将外排数组中的2，5拷贝进原数组
此时1,3,4和2，5要merge
左侧指针指向1
右侧指针指向2
右侧有2个数比1大 所以产生2个1的小和
将1拷贝到外排数组中
左侧置针移动到3
右侧的2小于3不产生小和 所以将2拷贝到外排数组
右侧下标移动到5
3小于5 右侧有一个数比3大 产生1个3的小和
把3拷贝到外排数组中
此时左侧下标指向4 右侧下标指向5
所以右侧还有一个5
对于4来说 右侧只有一个数5比4大 所以产生1个4的小和
将4拷贝进来
左侧指针再右移 下标越界 将右侧剩下的5拷贝进来
再拷贝进原数组
所以最终的排序是1，2，3，4，5
每次的小和分别是1，1，3，2，2，3，4 一共也是16
在merge的过程中 每一个数求有多少个数比这个数大的过程
是分批的 不遗漏的 也不重算 依次找到的
这里需要注意的地方是如果左侧和右侧相等的时候 一定要拷贝右侧且不产生小和
因为如果拷贝左侧 就不知道右侧有几个数比左侧大了
拷贝哪一侧 那一侧的指针就会往右移动
比如拷贝右侧 右侧指标p2往右移动 r-p2+1 就是右侧比左侧当前指针所指向的数大的个数
代码
当l=r的时候 小和就是0 也不需要排序
找中点位置
左侧排序并且求小和数量 加上 右侧排序并且求小和的数量
加上 左侧和右侧merge的过程产生小和的数量
就是整个小和的数量
1、
在两侧指针都不越界的情况下
只有左侧比右侧小
才产生小和数量增加的行为
增加多少呢
r-p2+1
表示当前右侧比当前左侧p1所指的数大的个数
个数乘以当前左侧所指的那个数就是小和增加的量
如果左侧不比右侧的小 小和增加的数量是0
2、接下来的拷贝：在当左侧比右侧小的时候 才拷贝左侧
当左侧大于等于右侧的时候 先拷贝右侧
3、越界或拷贝回原数组 过程不产生小和
