06 | 递归（下）：分而治之，从归并排序到MapReduce

老师讲的是最经典的2路归并排序算法，时间复杂度是O(NlogN)。如果将数组分解成更多组（假设分成K组），是K路归并排序算法，当然是可以的，比如K=3时，是3路归并排序，依次类推。3路归并排序是经典的归并排序（路归并排序）的变体，通过递归树方法计算等式T(n)= 3T(n/3)+ O(n)可以得到3路归并排序的时间复杂度为O(NlogN)，其中logN以3为底（不方便打出，只能这样描述）。尽管3路合并排序与2路相比，时间复杂度看起来比较少，但实际上花费的时间会变得更高，因为合并功能中的比较次数会增加。类似的问题还有二分查找比三分查找更受欢迎。

思考题： 如果不是分为两组，而是多组是可行的，但是处理起来比较麻烦。虽然分组的时候，能够更快完成，但是在合并的时候需要同时比较多组中的数据，取最小的一个。当分组数量比较大的时候，在合并的时候，为了考虑效率，需要维护一个堆来取最小值。假设分为N组，分组的时间复杂度是logn(N为底), 合并的时候时间复杂度为nlogN，总的时间复杂度不变，还是nlogn。不知道理解对不对，请老师指教！

老师，如果要排序的数组很大，两个最大的子节点排好序之后，交给最终的机器做最后的排序依然是一堆数据放在一个机器上

分成超过两个组的更多组是可行的，不过这样在递归调用时一个是有可能产生更多的中间状态数据，再一个在合并阶段，需要比较更多个分组的数据，实际上在最小粒度的时候，比较大小的就是两个数字，即便上层分成多个组，在合并的最底层依旧是从两两之间比较合并的，感觉分成多组的并没有啥优势，还带来了比较处理的复杂性

老师,你好 归并排序代码中有非空判断代码 if (a == null) a = new int[0]; if (to_sort == null) return to_sort; 什么情况下会出现数组是null??

分成多组归并，主要是合并比较会比较麻烦，会在合并时增加复杂度。比如比较2个数大小，只需要1次，而比较3个数大小，最多需要3次。

python实现代码： def mergeSort(list): if(len(list)==0): return 0 if(len(list)==1): return list[0] else: listHalfLen=int(len(list)/2) left=mergeSort(list[0:listHalfLen]) right=mergeSort(list[listHalfLen:]) data=merge(left,right) return data def merge(left,right): mid=[] ai=0 bi=0 if(isinstance(left,int)): leftLen=1 left=[left] else: leftLen=len(left) if(isinstance(right,int)): rightLen=1 right=[right] else: rightLen = len(right) while(ai < leftLen and bi < rightLen): if(left[ai]<right[bi]): mid.append(left[ai]) ai+=1 else: mid.append(right[bi]) bi+=1 if(ai< leftLen): newleft=left[ai:] for i in newleft: mid.append(i) else: newright = right[bi:] for i in newright: mid.append(i) return mid list=[3,8,5,9,7,1,10] mergeSort(list) 刚学python，希望大家多多指教

可以用数学方法证明二分归并排序是最优的应该。二分查找是可以证明的。 二分法我是这样证明的: https://ghostbody.github.io/posts/algorithmn/prove-binary-search-is-better/ 对于归并排序我还在思考利用主定理进行证明。 老师可以一起看下怎么证？

MapReduce 分割，映射，洗牌，归约这几个步骤没有具体的例子，就感觉不是很明白，希望这几个步骤还是用文章前半部分的排序的例子来分别举例

递归层次太多了，堆栈会溢出