这是谷歌面试问题：
给定 2 台机器，每台机器都有 64 GB RAM，包含所有整数（8 字节），对整个 128 GB 数据进行排序。您可以假设有少量额外的 RAM。扩展此功能以对存储在 1000 台机器中的数据进行排序。
我想出了外部排序。我们将整个数据分成块并对它们使用合并排序。这是首先对块进行排序，然后将它们放回去，然后再次分段并合并它们。有没有更好的办法？复杂程度如何？
ChingPing 提出对每个子集进行 O(n log n) 排序，然后进行线性合并（通过交换元素）。快速排序的问题（以及大多数 n log n 排序，是它们需要 n 内存。我建议改为使用平滑排序 http://en.wikipedia.org/wiki/Smoothsort它使用常量内存，仍然以 O(n log n) 运行。
最坏的情况是你遇到类似的情况：
setA = [maxInt .. 1]
setB = [0..minInt]
其中两个集合的顺序相反，但合并的顺序却相反。
ChingPing 解决方案的（IMO - 更清晰）解释是：
Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array
While setA's pointer is not at the end
if (setA[pointerA] < setB[pointerB])
then { pointerA++; }
else { swap(setA[pointerA], setB[pointerB]); pointerB++; }
现在这两个集合都应该已排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
