变量p1是左侧部分的下标指向L位置
变量p2是右侧部分的下标指向M+1位置
b、p1 没有超过M并且p2没有超过R 表示都没有越界
在都没有越界的情况下 谁小拷贝到help中去
p1位置的值 如果小于等于p2位置上的值
谁小则拷贝到help的i位置上去
假设p1位置上的值是1
p2位置上的值是3
1<3 则将1放到help的i位置上去
c、p1++ 就说明p1移动到了下一个位置
i++ 也来到了下一个位置
比如p1指向了4
4 >3 将3放到help i位置
d、i往下移动，p2也往下移动 比如指向了7
4<7 将4拷贝
e、如果p1没有越界 p2越界了
就把p1剩下的拷贝到help中去
或者 如果p2没有越界 p1越界了 就把p2剩下的拷贝到help中去
这2个while循环只会执行一个
要么p1越界要么p2越界
f、把help中的内容拷贝到原数组中
看这个过程是否可以用master公式
整个过程的数据量是N的规模
第一个子问题是N/2规模
第二个子问题也是N/2规模
即调用子问题调用了2次
除了子问题之外 剩下的过程是什么时间复杂度?
这个蓝色区域是O(1)时间复杂度
关键要看merge的时间复杂度是多少？
左侧指针只往右走不回退
右侧指针也是只往右走不回退
每一次只有一个指针动
左侧或右侧越界了之后 另一侧就把剩下的走完
所以整个过程是O(N)的时间复杂度
把help拷贝到数组中的过程也是O(N)的
所以整体的时间复杂度是
T(N)=2 * T(N/2) + O(N)
是符合master公式的 a=2,b=2,d=1
所以 = d
对应的时间复杂度是O(N * )
mergesort实质
选择排序、冒泡排序和插入排序 都是N^2的算法
为什么它们比mergesort差呢
因为它浪费了大量的比较行为
比如选择排序
0~N-1范围 比较了差不多N次 才知道哪个数放到0位置上
1～N-1次比较了N-1次 搞定一个数 放到1位置上
每一轮的比较都是独立的
比较这么多次 才搞定了一个数
归并排序没有浪费比较行为
归并排序是左侧的指针和右侧的指针
依次从左到右 左侧跟右侧的比
比较行为信息没有浪费 被留下来了
变成了整体有序的部分
正是因为这样的原因 它变成了O(N * )
外排序就是两个指针比较的东西拷贝到一个外部的数组中去，然后再拷贝回来
额外空间复杂度是O(N)表示最多只用准备N的空间就够了
每次merge的时候准备一个空间 用完就释放了
最多准备长度为N的空间 每一次复用该空间
题目
小和问题
[1,3,4,2,5]
1左边比1小的数 没有 所以1的小和是0
3左边比它小的数只有一个1 所以3的小和是1
4左边比它小的是1，3 累加为4 即4的小和是4
2左边比它小的只有一个1 ，2的小和是1
5左边都比它小 所以5的小和是1+3+4+2=10
整个数组的小和是所有小和累加起来
0+1+4+1+10=16
暴力解的方式
来到i位置的时候 左边遍历一下
所有比它小的都求出来
每到一个位置i 左边都遍历一下
等差数列
这样的方式时间复杂度是O(N^2)
求小和的过程能不能做到N*LogN
在mergesort的过程中就可以依次求出整个数组所有的小和来
比如 [1,3,4,2,5]
对1来说 右边有多少个数比1大呢
4个数 所以就产生4个1的小和
对3来说 右边有2个数比3大 所以产生2个3的小和
对于4来说 右边有1个数比4大 所以产生1个4的小和
对于2来说 右边有1个数比2大 生成1个2的小和
对于5来说 右边没有数 产生0个5的小和
一共还是16个小和
按照这样的思路求和原始问题是等效的
原来是求一个数左边有多少个数比它小都算作这个数的小和
反过来 求一个数 右边有多少个数比它大 依次求出它的小和
两者是等效的
一个数右边有多少个数比它大 可以用归并排序求解
对于[1,3,4,2,5]来说 1，3，4是左侧，2，5是右侧
对于1，3，4来说1，3是左侧，4是右侧
对于1，3来说1是左侧，3是右侧
对于2，5来说2是左侧，5是右侧
