- 2018-12-21老师讲的是最经典的2路归并排序算法，时间复杂度是O(NlogN)。如果将数组分解成更多组（假设分成K组），是K路归并排序算法，当然是可以的，比如K=3时，是3路归并排序，依次类推。3路归并排序是经典的归并排序（路归并排序）的变体，通过递归树方法计算等式T(n)= 3T(n/3)+ O(n)可以得到3路归并排序的时间复杂度为O(NlogN)，其中logN以3为底（不方便打出，只能这样描述）。尽管3路合并排序与2路相比，时间复杂度看起来比较少，但实际上花费的时间会变得更高，因为合并功能中的比较次数会增加。类似的问题还有二分查找比三分查找更受欢迎。
作者回复: 很好的回答👍
2 85 
2018-12-21思考题：
如果不是分为两组，而是多组是可行的，但是处理起来比较麻烦。虽然分组的时候，能够更快完成，但是在合并的时候需要同时比较多组中的数据，取最小的一个。当分组数量比较大的时候，在合并的时候，为了考虑效率，需要维护一个堆来取最小值。假设分为N组，分组的时间复杂度是logn(N为底), 合并的时候时间复杂度为nlogN，总的时间复杂度不变，还是nlogn。不知道理解对不对，请老师指教！作者回复: 用堆取最小值，思路不错
17
2018-12-24老师，如果要排序的数组很大，两个最大的子节点排好序之后，交给最终的机器做最后的排序依然是一堆数据放在一个机器上作者回复: 这里我有个细节没说清楚，如果数组是有序的，每次只需要从磁盘，有序的取出一部分到内存进行合并
10
2019-01-04老师,你好
归并排序代码中有非空判断代码
if (a == null) a = new int[0];
if (to_sort == null) return to_sort;
什么情况下会出现数组是null??作者回复: 在这个例子里不会出现，不过在实际工作中，这个函数可能被其他代码调用，为了保险起见，加一个最基本的非法检测
8
2018-12-28python实现代码：
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，希望大家多多指教展开作者回复: 作为初学者，写得很不错👍
7
2018-12-21分成超过两个组的更多组是可行的，不过这样在递归调用时一个是有可能产生更多的中间状态数据，再一个在合并阶段，需要比较更多个分组的数据，实际上在最小粒度的时候，比较大小的就是两个数字，即便上层分成多个组，在合并的最底层依旧是从两两之间比较合并的，感觉分成多组的并没有啥优势，还带来了比较处理的复杂性作者回复: 是的 有读者说可以用堆来取多个组的最小值，虽然可行，但确实比较复杂
7
2019-01-08分成多组归并，主要是合并比较会比较麻烦，会在合并时增加复杂度。比如比较2个数大小，只需要1次，而比较3个数大小，最多需要3次。作者回复: 是的👍
5
2019-01-06递归层次太多了，堆栈会溢出作者回复: 是的 需要转换成循环 或者栈的数据结构
5
2018-12-29# 切分
def split_list(temp_list):
if not isinstance(temp_list, list):
raise TypeError
else:
if not temp_list:
raise ValueError
else:
length = len(temp_list)
if length == 1:
return temp_list
import math
left = math.ceil(length / 2)
del math
left_list = split_list(temp_list[:left])
right_list = split_list(temp_list[left:])
return merger_list(left_list, right_list)
# 归并
def merger_list(left, right):
result = []
while True:
if left and right:
left_0 = left[0]
right_0 = right[0]
if left_0 > right_0:
min_num = right.pop(0)
else:
min_num = left.pop(0)
result.append(min_num)
elif left:
result.append(left.pop(0))
elif right:
result.append(right.pop(0))
else:
break
return result
print(split_list([3, 1, 2, 7, 4, 6, 9, 9, 10, 11, 4, 5]))展开 4
2018-12-21上学只上到初二，已经十几年没学习数学了。自从做了3年程序员，一碰到数学问题就头痛。 4
2019-02-19MapReduce 分割，映射，洗牌，归约这几个步骤没有具体的例子，就感觉不是很明白，希望这几个步骤还是用文章前半部分的排序的例子来分别举例作者回复: 这个概念涉及了比较多分布式系统的设计，我可以在后面加餐内容放入一些，或者是放到实战篇内容补上
3
2019-01-09/*
* 采用分而治之思想实现数组排序, 递归为其实现技巧
*/
#include <iostream>
using namespace std;
void merge(int *array, int low, int mid, int high) {
// left: low ~ mid, right: mid+1 ~ high
int size = high - low + 1;
int *tmp = new int[size];
int i = low, j = mid+1, k = 0;
while (i <= mid && j <= high) {
if (array[i] <= array[j]) {
tmp[k++] = array[i++];
} else {
tmp[k++] = array[j++];
}
}
// the rest elements
while (i <= mid) {
tmp[k++] = array[i++];
}
while (j <= high) {
tmp[k++] = array[j++];
}
// copy the elements to original array
for (k = 0; k < size; ++k) {
array[k+low] = tmp[k];
}
}
void _mergeSort(int *array, int low, int high) {
if (low >= high) return;
int mid = low + ((high-low) >> 1);
_mergeSort(array, low, mid);
_mergeSort(array, mid+1, high);
merge(array, low, mid, high);
}
void mergeSort(int *array, int size) {
cout << "*****************before**************" << endl;
for (int i = 0; i < size; ++i) {
cout << array[i] << " ";
}
cout << endl;
_mergeSort(array, 0, size-1);
cout << "*****************after**************" << endl;
for (int i = 0; i < size; ++i) {
cout << array[i] << " ";
}
cout << endl;
}
int main() {
int array[] = {2, 3, 5, 1, 4, 9, 7, 6, 10};
mergeSort(array, 9);
return 0;
}
*****************before**************
2 3 5 1 4 9 7 6 10
*****************after**************
1 2 3 4 5 6 7 9 10展开作者回复: 实现的思路很清晰，还用到了位移操作👌
3
2018-12-24老师您好，归并这种，比如数组排序无限的对半分开，这样会不会性能反而不如对半分开到一定程度，剩下的用别的排序算法，应该有一个平衡点吧作者回复: 这是个好的想法，我觉得和实际数据的分布有关，不同的分布可以找到不同的平衡点，不过本身要测算数据的分布可能更耗时间。如果事先知道了数据的特点，应该是可以结合不同的排序来优化
3
2019-06-21和快排对比，虽然时间复杂度都是nlogN，但是归并排序的空间复杂度是O(n)，快排则是原地排序。不过归并排序是稳定排序，快排则不是，两种各有优势。作者回复: 很好的比较
1 2
2019-06-01可以用数学方法证明二分归并排序是最优的应该。二分查找是可以证明的。
二分法我是这样证明的: https://ghostbody.github.io/posts/algorithmn/prove-binary-search-is-better/
对于归并排序我还在思考利用主定理进行证明。
老师可以一起看下怎么证？展开作者回复: 第一次看到读者证明二分法是最优的，赞一个。至于归并排序应该是类似的，唯一不同的是，归并的合并过程也有一个复杂度要计算，而不是像比较大小那样O(1)
1
2019-02-13通过这一节的阅读学习，对归并排序算法有了理解。本质上就是二步，先分后和。而分开的过程中使用的分治的思想，实现分开中用递归的方法来实现。合并把函数结果返回。
在大数据领域中，HDFS和MapReduce中都使用了这种分治的思想，把数据集划分给不同的机器，每台机器把数据分成许多块，Yarn调用程序让MR处理对应的数据，达到对海量数据的处理。
目前需要做的就是理解之后花些时间实践，这样在原理的基础上更好的去理解。 1
2019-01-11js 写的代码
function guibingorder(arr) {
if (arr.length > 1) {
var leftarr = [];
var rightarr = [];
var splitindex = Math.floor(arr.length / 2);
leftarr = arr.slice(0, splitindex);
rightarr = arr.slice(splitindex, arr.length);
leftarr = arguments.callee(leftarr);
rightarr = arguments.callee(rightarr);
var result = [];
while (Math.max(leftarr.length, rightarr.length) > 0) {
//右边遍历完了 或者 左边比右边的小，则 从左边取出来
if (rightarr.length == 0 || leftarr[0] < rightarr[0]) {
result.push(leftarr[0]);
leftarr.splice(0, 1);
} else {
result.push(rightarr[0]);
rightarr.splice(0, 1);
}
}
return result;
}
return arr;
}展开作者回复: 逻辑上很清晰
1 1
2019-01-01思考题：一分为二，是为了处理起来简单，这样也就有了更好的通用性；当然，分成很多也是可行的，但是在数学上，它们是等价的。这个问题类似于在算法领域只研究二叉树 1- 2018-12-29# python实现
# 切分
def split_list(temp_list):
if not isinstance(temp_list, list):
raise TypeError
else:
if not temp_list:
raise ValueError
else:
length = len(temp_list)
if length == 1:
return temp_list
import math
left = math.ceil(length / 2)
del math
left_list = split_list(temp_list[:left])
right_list = split_list(temp_list[left:])
return merger_list(left_list, right_list)
# 归并
def merger_list(left, right):
result = []
while True:
if left and right:
left_0 = left[0]
right_0 = right[0]
if left_0 > right_0:
min_num = right.pop(0)
else:
min_num = left.pop(0)
result.append(min_num)
elif left:
result.append(left.pop(0))
elif right:
result.append(right.pop(0))
else:
break
return result
print(split_list([3, 1, 2, 7, 4, 6, 9, 9, 10, 11, 4, 5]))展开作者回复: Python的实现 不错
1 - 2018-12-24哈哈 这个问题我记得当初公司宿舍聊过，分组多的话单从复杂度计算上是降低了，舍友（做硬件安全的）告诉我说是因为计算机是二级制的，底层处理上实际上多分组是效率低的。至今不明白其中的缘由，希望老师指点^^ 1