如何对价值 100GB 的字符串进行排序

解答 1.您可能希望实现某种形式的合并排序。

A2：比计算机上有256GB RAM时更长。

编辑：被批评刺痛，我引用维基百科关于合并排序的文章：

合并排序本质上是顺序的，因此使用慢速磁带驱动器作为输入和输出设备来运行它是可行的。它需要很少的内存，并且所需的内存不依赖于数据元素的数量。

出于同样的原因，它对于对磁盘上的数据进行排序也很有用，这些数据太大而无法完全放入主内存中。在可以向后和向前运行的磁带驱动器上，合并传递可以在两个方向上运行，从而避免了倒带时间。

以下是我的做法：

阶段 1 是将 100Gb 拆分为 50 个 2Gb 分区，将 50 个分区中的每个分区读取到内存中，使用快速排序进行排序，然后写出。您希望将排序的分区放在光盘的顶端。

第 2 阶段是合并 50 个已排序的分区。这是一个棘手的问题，因为光盘上没有足够的空间来存储分区和最终的排序输出。所以。。。

1. 执行 50 路合并以填充光盘底端的第一个 20Gb。

2. 将 50 个分区中的剩余数据滑到顶部，使另外 20Gb 的可用空间与前 20Gb 分区的末尾保持连续。

3. 重复步骤 1。和 2.直到完成。

这会产生大量的光盘 IO，但您可以在复制和合并步骤中利用 2Gb 内存进行缓冲，通过最大限度地减少磁盘查找次数来获得数据吞吐量，并进行大型数据传输。

编辑 - @meriton提出了一种减少复制的聪明方法。他建议将分区按相反的顺序排序，并在合并阶段向后读取，而不是滑动。这将允许算法通过简单地截断分区文件来释放分区使用的磁盘空间（阶段2，步骤2）。

这样做的潜在缺点是增加磁盘碎片，以及由于向后读取分区而导致性能损失。（在后一点上，在Linux / UNIX上向后读取文件需要更多的系统调用，而FS实现可能无法在相反的方向上进行“提前读取”。

最后，我想指出，对这个算法（和其他算法）所花时间的任何理论预测在很大程度上都是猜测。这些算法在真实JVM + 真实操作系统 + 真实光盘上的行为太复杂了，无法给出可靠的答案。适当的处理需要实际的实施、调整和基准测试。