我正在读关于MapReduce和下面的事情是混淆了我。
假设我们有1万个条目（整数）的文件，我们希望使用MapReduce的对它们进行排序。我的理解去了解它的方式如下：
编写排序整数一个映射功能。因此，该框架将划分输入文件分成多个块，将给予他们不同的映射器。每个映射器将整理他们的数据相互独立的块。一旦所有的地图制作完成后，我们将通过他们的每一个结果来减速，这将结果结合起来，给我的最终输出。
我的疑问是，如果我们有一个减速，那么它是如何利用分布式架构，如果，最终，我们要的结果在一个地方结合起来？这个问题可以深入到一个地方合并百万条目。是这样还是我失去了一些东西？
谢谢你，钱德
看看合并排序。
事实证明，部分排序排序的列表是在操作和内存消耗比排序的完整列表方面更有效。
如果减速获得4名有序列表，只需要认准4所列出的最小元素并挑选一个。如果列表的数目是恒定的这种减少是O（N）的操作。
也通常是减速也“分布式”的东西就像一棵树，所以工作也得以parrallelized。
正如其他人所说，合并是比排序要简单得多，所以有一个巨大的胜利那里。
然而，在一个巨大的数据集做一个O（N）串行操作可以是望而却步了。当你正确地指出，最好是找到一种方法，做平行合并，也是如此。
要做到这一点的方法之一是从随机分区（这是什么正常使用）的东西有点聪明替换分区功能。这个做什么猪，例如，是抽样数据集来与你的价值观分布的粗略近似，然后分配值的范围不同的减速。减速器0得到的所有元素<1000，减速机1得到的所有元素> = 1000和<5000，依此类推。然后，你可以做平行合并，并为您知道每个减速器任务的数量最终结果进行排序。
所以，最简单的方法来排序使用的map-reduce（虽然不是最有效的一种）是做到以下几点
在映射阶段（Input_Key，将input_value）发出了（将input_value，输入键）
减速机是一种身份减速
因此，举例来说，如果我们的数据是学生，年龄数据库那么你的映射器的输入是（“A”，1）（“B”，2）（“C”，10）...和输出是（1， A）（2，B）（10，C）
有没有试过这种逻辑了，但它是在我工作的一个家庭作业问题的步骤。将会把更新源代码/逻辑链接。
对不起，我来晚了，但对于未来的读者，是的，钱德尔，你失去了一些东西。
逻辑是，减速机可处理混洗，然后仅排序其上运行其节点的数据。我的意思是，在一个节点上运行不能看其他节点的数据减速机，它适用于只减少它的数据算法。所以合并排序的合并过程不能被应用。
因此，对于大数据，我们使用TeraSort，这不过是身份映射器和减速机采用定制的分区。你可以阅读更多关于它在这里Hadoop's implementation for TeraSort。它指出：
“TeraSort是一个标准的地图/排序减少，除了使用N的排序列表的自定义分区 - 定义键的范围为每减少1个采样键特别地，所有的键，使得样品[I - 1] <=键<样品[I]被发送，以减少I。这保证了的输出减小I都小于的输出减少I + 1“。
我认为，结合多种排序项比合并多个未排序项有效。因此，映射器做排序块的任务和减速将它们合并。已经映射器没有做排序，减速将有艰难的时间做整理。
排序可以使用MapReduce的高效实现。但你似乎是考虑实施合并，排序使用的MapReduce来实现这一目的。这可能不是理想的人选。
就像你提到，归并（带的map-reduce）将包括以下步骤：
这里的问题是，像你提到的，只能有一个减速这在还原过程排除了并行性。就像是在其他答复中提到，MapReduce的具体实现像terasort可以考虑用于此目的。
发现在http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf解释
回来合并排序，这将是可行的，如果Hadoop的（或相当的）工具提供减速的层次结构中减压器一级的输出变为减速或循环它的一个新的水平回到同一组减速器