algorithm - 排序大于 RAM 大小的数据

Question

这是一个谷歌面试问题: 给定 2 台机器，每台机器都有 64 GB RAM，包含所有整数(8 字节)，对整个 128 GB 数据进行排序。您可以假设有少量额外的 RAM。扩展它以对存储在 1000 台机器中的数据进行排序。

我想到了外部排序。因为我们将整个数据分成 block 并对它们使用合并排序。这是第一次对 block 进行排序，然后将它们放回去，然后再次分段获取它们并合并它们。有没有更好的办法？复杂度如何？

Answer 1

ChingPing 建议对每个子集进行 O(n log n) 排序，然后进行线性合并(通过交换元素)。 Quicksort(以及大多数 n log n 排序)的问题是它们需要 n 内存。我建议改用 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++; }

这两个集合现在应该都已排序。