排序是将元素从某种顺序的集合中放置元素的过程。例如，一个单词的列表可以按字母或长度。一个城市列表可以按人口，按地区，或由邮政编码。我们已经看到了一些算法，能够在排序列表中受益（回忆最终字谜的例子和二进制搜索）。 有许多，许多排序算法，已开发和分析。这表明，排序是计算机科学研究的一个重要领域。分类大量的项目可以采取大量的计算资源。与搜索一样，排序算法的效率与正在处理的项目的数量有关。对于小集合，一个复杂的排序方法可能会比它更麻烦。开销可能太高。另一方面，对于较大的集合，我们希望利用尽可能多的改进。在这一节中，我们将讨论几种排序技术，并将它们与它们的运行时间进行比较。
##排序分析 在进入特定的算法之前，我们应该考虑可以用来分析一个排序过程的操作。首先，它将有必要比较两个值，看哪一个较小（或更大）。为了对集合进行排序，它将需要有一些系统的方法来比较值，看看他们是否是出于秩序。比较的总数将是最常见的方法来衡量一个排序程序。第二，当值不在正确的位置相对于彼此，它可能是必要的，以交换他们。此交换是一个昂贵的操作和总的交流数也将是重要的，以评估该算法的整体效率。
##排序之最
Google怎么样做50PB数据排序的?
自从创造 MapReduce 以来，我们就通过对海量随机数据进行排序来测试它。我们喜欢排序，因为很容易生成任意数量的数据，检查输出是否正确同样简单。
尽管最初的 MapReduce 论文提交了一个 TeraSort 结果。工程师定期通过对 1TB 或者 10TB 的数据排序来做回归测试。因为数据量越大，那些不易察觉的 bug 越容易显现。然而，当我们进一步扩大规模后，乐趣开始显现。本文会回顾前几年我们做的一些 PB 量级测试的经历。这其中包括 MapReduce 迄今为止做过的最大量级的测试：50PB 数据的排序。
如今，GraySort 已经是海量数据排序的基准。使用 GraySort，以最快的速度按照字典顺序对至少 100TB 的数据进行排序（100字节的记录，开头10个字节作为关键字）。网站 sortbenchmark.org 记录了基于此基准的官方获胜者。但谷歌从未参加官方竞赛。
由于 MapReduce 就是通过对键排序来缩减规模，因而它很适合解决这个问题。通过合适的（词典）分片功能，MapReduce输出一系列包含最终排序后数据集的文件。
有时在数据中心有新集群出现时（一般是搜索索引团队使用）， 我们 MapReduce 组员就可以在动手干活前玩上几下。我们有机会试试让集群超负荷，测试硬件的极限范围，搞挂掉一些硬盘，测试一些非常昂贵的设备，学到很多关于系统性能的东 西，同时获得排序基准竞赛的胜（非官方）。
2007年
（1PB，12.13 小时，1.37 TB/分钟，2.9 MB/秒/worker）
我们在 2007 年进行了首次 Petasort 测试。那时我们很开心能够完成整个测试，尽管对输出结果的正确性有些质疑（我们并没有验证正确性）。要不是我们关闭了验证 map 分片输出结果与备份是否一致的机制，就无法完成这项工作。我们怀疑这是用来对输入输出数据排序的谷歌档案系统（GFS）所造成的限制。GFS没 有足够的校验和保护机制，有时会返回坏值。糟糕的是，该基准所采用的文本格式并没有自带的校验和，来让 MapReduce 发送通知（在谷歌，MapReduce 的使用方式一般都是采用内嵌校验和的文件格式）。
2008年
（1PB，6.03 小时，2.76 TB/分钟，11.5 MB/秒/worker）
2008 年开始，我们开始着眼于优化调整。我们花了几天时间来调整分片数量、各个缓存区的大小、预读/预写机制、页缓存机制等等。通过向 GFS 三路复制输出结果我们解决了瓶颈，这也是我们那时在谷歌的标准用法。少任何一路都会带来很高的风险。
2010年
（1PB，2.95 小时，5.65 TB/分钟，11.8 MB/秒/worker）
在测试中，我们使用了新版本的GraySort基准，它采用不可压缩的数据。在早些年，我们从 GFS 读取或写入 1 PB的数据时，实际传输的数据只有 300 TB，因为那时所使用的ASCII格式易于压缩。
这也是 Colossus 诞生的一年（谷歌下一代分布式存储系统，GFS 的继任者）。我们不会再遇到先前使用 GFS 时碰到的崩溃问题。我们还对输出结果进行RS编码（Colossus的新功能），从而将总写入据量从 3 PB（三路复制）减少到大约1.6PB。我们也首次验证了输出结果的正确性。
为了减少掉队数据的影响，我们采用动态分片技术（也被称作 reduce subsharding）。这也是后来在 Dataflow 所采用的全动态切片技术的先驱。
2011年
（1PB，0.55 小时，30.3 TB/分钟，63.1 MB/秒/worker）
这 一年我们的网络速度更快，也开始更多地关注每台服务器的效率，特别是输入/输出（I/O）方面的问题。我们确保了所有的磁盘读写操作都是在 2 MB 的区块中进行，而不会落到 64 KB 的小区块中。我们使用固态硬盘来存储部分数据。这使得 Petasort 测试首次在一小时时间内完成––确切讲是 33 分钟––我们在此做了介绍。最终，在分布式存储中输入/输出以及坚持将中间数据保存在硬盘中以支持容错（由于在这种规模的测试中，某些硬盘甚至整台服务器都很容易宕掉，因此容错非常重要）的问题上，性能几乎达到了在指定 MapReduce 架构条件下的硬件极限性能的两倍。
同时也获得了更高的扩展：我们在 6 小时 27 分钟之内运行了 10 PB 的数据（26 TB/分钟）。
2012年
（50PB，23小时，36.2TB/分钟，50 MB/秒/worker）
在这个测试中，我们将注意力转移到更大规模的测试中。通过调用我们在谷歌所能获取到的最大规模集群，我们进行了最大规模的 MapReduce 测试（就分片数据量而言）。不幸的是，该集群没有足够的硬盘空间来对 1000 PB 的数据进行排序，因而我们将排序的数据量限定在 50 PB。我们只测试了一次，也没有做专门的优化，参数设置还沿用了之前 10 PB 测试的那套。完成时间为 23 小时 5 分钟。
注意，这个排序的规模是GraySort大规模标准 的500倍，在吞吐量上是2015年GraySort官方优胜者的两倍。