归并排序的原理并不是很复杂，他的意思是说，将一个数组从中间分解成左右两个部分，然后对左右两部分分别排序，将排序后的结果再进行合并。
我们先来讨论经典的递归实现方法。
归并排序的递归实现可以总结为：左边排好序+右边排好序+merge让总体有序
这个问题最大的困难就是如何进行合并merge,我们通过画递归树可以知道，最后一定是一个元素和一个元素进行的merge,那么这个merge的过程还需要涉及到对这两个元素进行比较，那么如何去实现呢？
这里我们采用双指针法和辅助数组的方式，首先创建一个辅助数组，左右两个元素分别创建辅助指针，如果左边的元素小，先进入数组，后移，右边的小右边的先进，后移，同样大小，左边的进去，同时后移。
归并排序的复杂度是O(NlogN)
merge过程两个指针都没有回退, 是O(N)
比较行为每一次变成结果再传递, 没有浪费(相比N^2的算法)
为什么比O(N^2)的排序好，最本质的原因是所有O(N^2)的排序，大量浪费比较行为比较行为都是独立的. 上一次发生的比较行为，丝毫不能够加速底下的比较行，大量浪费比较行为
与 插入, 冒泡, 选择等N^2排序的比较
选择等每次排序相对独立,大量浪费比较行为
把有序部分规定/留下来, 没有浪费比较行为
而归并排序 我左组内部的比较行为浪费了吗？没浪费, 都变成了排序好的结果，右侧部分也变成了排序好的结果。当你左侧跟右侧Merge的过程中，左组数之间是根本没有比较的，要比较是左组某一个指针对右组某一个指针在比较，你们此时比较行为也没有浪费, 变成了你们共同的一个排好序的结果，所以比较行为每一次都变成结果在传递,所以复杂度是O(N*logN)
额外空间复杂度为O(N)
现在看看代码
class MergeSort{
public static void mergeSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
process(arr,0,arr,length - 1);
}
public static void process(int[] arr,int left,int right){
if(right == left){
return ;
}
int mid = left + ((right - left) >> 1);
process(arr,left,mid);
process(arr,mid+1,right);
merge(arr,left,mid,right);
}
public static void merge(int[] arr,int left,int mid,int right){
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;//用于记录数组位置
while(p1 <= mid && p2 <= right){
help[i++] = arr[p1] >= arr[p2] ? arr[p2++] : arr[p1++];
}
//左右两个哪一个没有完全进入数组
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= right){
help[i++] = arr[p2++];
}
for(i = 0;i < arr.length;i++){
arr[left + i] = help[i];//注意这个小细节
}
}
}下面我们来看看不使用递归又是一个什么思路
当我们不适用递归的时候，我们需要使用一个步长的变量，涉及步长变量，步长为1，相邻两个一组去做merge,步长超过数组长度停止。
步长的变化次数为logN
这里还需要注意的是防止步长的溢出
class MergeSort{
public void mergeSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int N = arr.length;//数组长度
int mergeSize = 1;//步长
while(mergeSize < N){
//当前所处左组第一个位置，步长变化为logN
int L = 0;
while(L < N){
if(mergeSize >= N-L){
break;
}
int M = L + mergeSize - 1;//M是这样的出的，其实就是求和除2的意思，只不过我们知道的步长
int R = M + Math.min(mergeSize,N - M - 1);
merge(arr,L,M,R);
L = R + 1;
}
//防止溢出
if(mergeSize > N/2){
break;
}
//变成2^
mergeSize <<= 1;
}
}
public static void merge(int[] arr,int left,int mid,int right){
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;
while(p1 <= mid && p2 <= right){
help[i++] = arr[p1] >= arr[p2] ? arr[p2++] : arr[p1++];
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= right){
help[i++] = arr[p2++]
}
for(i = 0;i < arr.length;i++){
arr[left + i] = help[i];
}
}
}现在看一个经典的数组小和问题：
【1，3，4，2，5】这一个数组
左边比1小的数为0，小和为0
3为1，4为4，2为1，5为10，所以整个数组小和为16.
我们可以采用依次遍历的方式，但是时间复杂度为O(n^2)，那有没有更快的方式呢？
现在我们转换一下思路：
在前面这个数组中，比1大的数又四个，3又2个，4有1个，2有1个，5为0个
1*4+3*2+4*1+2*1+5*0 = 16也等于16。所以我们可以这样转换过来。
这是这个递归树，当为1,3的时候，产生了1个1，3进入数组，然后13和4，产生1个1，一个3，变成134，然后2,5产生1个2变成25
然后134和25,产生2个1，一个3，一个4。加一块一共十六。
这里还要一个点需要注意，就是排序的过程是不能省略的。我们只要排序好，才能通过O（1）的时间计算出有多少个数比他大。
class SmallSum{
public static int smallSum(int[] arr){
if(arr == null || arr.length < 2){
return -1;
}
return process(arr,0,arr.length - 1);
}
public static int process(int[] arr,int left,int right){
if(left == right){
return 0;
}
int mid = left + ((right - left) >> 1);
return process(arr,left + mid)+process(arr,mid+1,right)+merge(arr,left,mid,right);
}
public static int merge(int[] arr,int left,int mid,int right){
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int res = 0;
int i = 0;
while(p1 <= mid && p2 <= right){
res += arr[p1] < arr[p2] ? arr[p1] * (right - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= right){
help[i++] = arr[p2++];
}
for(i = 0;i < arr.length;i++){
arr[left + i] = help[i];
}
return res;
}
}再看一个题目
求一个数组中所有的逆序对
什么叫逆序对呢，你是左边的数比右边的大就是逆序
看个图：
经典的办法就是在merge的时候从右往左，左组跟右组比较，谁大就拷贝谁，相等的话先拷贝右组，左组大拷贝左组，产生逆序对，右组大拷贝右组，不产生逆序对。
相等的时候先拷贝右边的, 右组指针到4, 左组为6 此时, 针对左组的6有3个数比他小
给定一个数X, 求右边到底有多少个数比 X 小?以X作为第一个数的情况下，第二个数你能选哪些? 所有比他小的数都能够跟他构成逆序对所以我一定要严格纠结 X 右边所有范围上有多少数比 X 小如果我 X 是右组姿态, 跟某一个左组合并, 不会有关于x逆序对产生因为X关心的是右边范围上有多少个数比我小而不关心左边范围上有多少个数比我小。所以 X 作为右组姿态是一定不会产生逆序对的你怎么达成目标。从右往左拷贝
看看代码：
class ReversePair{
public static int reversePair(int[] arr){
if(arr == null || arr.length < 2){
return 0;
}
return process(arr,0,arr.length - 1);
}
public static int process(int[] arr,int L.int R){
if(L == R){
return 0;
}
int mid = L + ((R - L) >> 1);
return
process(arr,L,mid) + process(arr,mid + 1,R) + merge(arr,L,mid,R);
}
public static int merge(int[] arr,int L,int mid,int R){
int p1 = mid;
int p2 = R;
int i = arr.length - 1;
int res = 0;
while(p1 >= L && p2 >= mid + 1){
res += arr[p1] > arr[p2] ? (p2 - mid) : 0;
help[i--] = arr[p1] >= arr[p2] ? arr[p1--] : arr[p2--];
}
while(p1 >= L){
help[i--] = arr[p1--];
}
while(p2 >= R){
help[i--] = arr[p2--];
}
return res;
}
}再来看一题，数组中的数，他的右边有多少个数乘2依旧小于number这个数的？
思路就是砍一半，左边产生的个数+右边产生的个数+merge的个数
public static int merge(int[] arr,int L,int m,int R){
int ans = 0;
//注意windowR的区间位置[m+1,windowR)左闭右开
int windowR = mid + 1;
for(int i = L;i <= m;i++){
//左边的数跟右边的比较
while(windowR <= r && arr[i] > (2*arr[windowR])){
windowR++; //算出个数
}
ans += windowR - m - i;
}
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int res = 0;
int i = 0;
while(p1 <= mid && p2 <= right){
//res += arr[p1] < arr[p2] ? arr[p1] * (right - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while(p2 <= right){
help[i++] = arr[p2++];
}
for(i = 0;i < arr.length;i++){
arr[left + i] = help[i];
}
return ans;
}总结
MergeSort这几道题思路要不要背下来?
一开始对于新手来说，背下来可能是一种必然。但实际上你写了之后，MergeSort类似
比如我们你们三道题你带来什么启示，当你想求一个数，右边怎么样的时候，整体个数的时候你是不是都想往MergeSort靠，我讲这题是在给你搞一种原型？只要一个指标一个问题，它是根据每一个数右边或左边整个范围上求几个这个玩意的他可能下回换了个新面貌，但只要是跟这个流程有关，都往往MergeSort靠
你要知道Coding的这个技巧，真是练很长时间才能够才能会说有点感觉你比如我今天讲的不回退的技巧，来自于单调性。左组的数从小数开始依次考察大数的过程中, 右边也有序，所以那个R是可以不回退的。单调性这种东西往往就跟不回退有关。你在写的过程中逐渐去形成这样一种Code的思想的这个东西我给你练的题给你讲这东西，一定要练熟, 因为，太常见了