昨天面的一道题目，大家一起讨论下

[darouwan]

题目是分布式排序 已知有 n 个节点，每个节点有长度为 m 的数组。m<<n

现在对这 m*n 个数据进行排序。

我一开始用归并排序，但考官说不行。大家有什么好的解决方案？

[AFuture]

先来一波置换选择，再来一波最佳归并。以上仅一个菜鸡本科学生的观点。

[ytmsdy]

m<<n
这个表达的意思是不是 M 远远小于 N
如果是这样的话，需要先把所有的数都拿出来，然后在做排序。
简单一点说就是我要对 1w 个数字进行排序，但是每个数组里面只有 2 到 3 个元素，这种情况下，归并排序并不适合。

[ytmsdy]

1w 个数字进行排序=====> fix 1w 个数组

[darouwan]

@ytmsdy 是的，m 远小于 n，所以不能频繁遍历 n

[darouwan]

@ytmsdy 要求不能一次性吧所有数字取出来，空间不够的。

[ksco]

在楼主的已知条件之上做一些假设。

假设每台机器都有一个固定的编号：1, 2, ..., n。
排序完成后，我们的目标是可以产生一个有序的“流”，因为内存装不下。

方案如下：
首先给每个节点的数组排序，这个没啥好说的。
然后维护一个最小堆，堆的元素是 (节点编号, 当前下标, 具体数值) 这样的一个三元组，当然堆的排序依据是“具体数值”。

排序的方法是，每次从堆里面弹出一个最小的元素，放入流中，再把这个元素的当前下标步进 1，取该下标的值，生成新的三元组放回堆中，然后循环。


===
最后无耻一下：我做了个公众号“每天一道编程题”，欢迎关注～

[ksco]

补充一下，这个方法应该叫 k-way merge

https://en.wikipedia.org/wiki/K-way_merge_algorithm

[zjxlim]

@ksco 败者树？

[shidenggui]

这个应该是属于 external sorting 里面的 k-way merge。下面的算法来自《 Data Structures and Algorithm Analysis in C 》:

首先令 N = m * n 表示所有需要排序的量，M 表示内存能容纳的最大数据量。

然后在内存中维护一个最小堆，第一次读 M / m 个节点，将最小堆填充满，然后每次 pop 一个最小的值依序写入到对应的节点中，这时内存中会多出一个空位，此时可以继续读取数据，如果读取的值大于 pop 出的最小值，则将其加入最小堆参与这一轮的排序，否则将其留在 pop 出最小值后留下的 dead space 中，等待下一轮排序。

这里有一个问题是每个节点应该写入多少次排序好的数组呢？比如都写入一次，则需要读取的节点数太多了。根据书上的方法，根据 N / M 估计第一次排序产生的数组数量，然后计算 kth order 斐波那契数列。比如有 N / M 为 34，两个节点，则第一个节点写入 21 组，第二个节点写入 13 组。

然后按照同样的逻辑不断归并，最后就可以得到一个有序数组。

整体算法复杂度为 O(Log_k{N/M})，k 为节点数。

[vansl]

堆

[vegito2002]

k-merge. map reduce 和 sstable 的实现里面我记得都有用到这个原理

[binux]

啊，归并排序为什么要遍历 n ？即使是两路归并你还不是要记录现在的左右值，难道去遍历吗？和所谓的 k-way merge 有什么区别？
多路也一样啊，即使不建堆，比起节点读取速度，插入排序也没什么嘛。我还以为面试官要求 n 的读取呢

[darouwan]

@ksco 有一个地方没看懂, 为什么是"再把这个元素的当前下标步进 1，取该下标的值"?
比如说 我现在 2 个节点 数据分别是
1 5 6
2 3 4
第一轮 1,2 最小构成堆, 弹出 1, 那下一个岂不是 5?

[darouwan]

@ksco 哦~看了下懂了 等于说输出最小值之后, 次小值要么在以构建的堆里, 要么在最小值所在的节点里