Merge sort is so inherently sequential that it is practical to run it using slow tape drives as input and output devices. It requires very
little memory, and the memory required does not depend on the number
of data elements.
For the same reason it is also useful for sorting data on disk that is
too large to fit entirely into primary memory. On tape drives that can
run both backwards and forwards, merge passes can be run in both
directions, avoiding rewind time.
# 1 楼答案
我觉得你应该用BogoSort。您可能需要稍微修改算法以允许就地排序，但这应该不会太难。：）
# 2 楼答案
您应该使用trie（又名：前缀树）：构建一个树状结构，通过比较字符串的前缀，可以轻松地按顺序遍历字符串。事实上，你不需要把它存储在内存中。您可以将trie构建为文件系统上的目录树（显然，不是数据来源的目录树）
# 3 楼答案
我基本上是在重复Krystian's answer，但详细阐述：
是的，你需要或多或少地在适当的地方这样做，因为你几乎没有可用的内存。但单纯的就地排序在这里会是一场灾难，因为移动字符串的成本太高
不要实际移动字符串，只需跟踪哪些字符串应该与哪些其他字符串交换，并在最后一次实际移动到它们的最终位置。也就是说，如果有1000个字符串，那么就创建一个1000整数的数组。数组[i]是字符串应该结束的位置。如果最后的数组[17]==133，则表示字符串17应该位于字符串133的位置。数组[i]==i表示所有i开始。因此，交换字符串只是交换两个整数的问题
然后，任何像quicksort这样的就地算法都能很好地工作
跑步时间肯定是由琴弦的最后一步决定的。假设每一个数据都在移动，那么在大小合理的写操作中大约移动了100GB的数据。我可能会假设驱动器/控制器/操作系统可以为您移动大约100MB/秒。1000秒左右？20分钟
但它是否符合记忆？您有100GB的字符串，每个字符串是256字节。有几根弦？100*2^30/2^8，或大约419M的字符串。你需要4.19亿个整数，每一个都是4字节，大约1.7GB。瞧，适合你的2GB
# 4 楼答案
以下是我的做法：
第一阶段是将100Gb分成50个2Gb的分区，将50个分区中的每一个都读入内存，使用快速排序进行排序，然后写出。您希望将已排序的分区放在光盘的顶端
第二阶段是合并50个已排序的分区。这是一个棘手的问题，因为磁盘上没有足够的空间来存储分区和最终排序的输出。所以
进行50路合并，以填充光盘底端的前20Gb
将50个分区中的剩余数据滑动到顶部，使另一个20Gb的可用空间与前一个20Gb的末尾相连
重复步骤1。和2。直到完成
这会产生大量的磁盘IO，但您可以在复制和合并步骤中利用2Gb内存进行缓冲，通过最小化磁盘搜索次数获得数据吞吐量，并进行大数据传输
EDIT-@meriton提出了一种减少复制的聪明方法。他建议在合并阶段将分区按相反顺序排序并向后读取，而不是滑动。这将允许算法通过简单地截断分区文件来释放分区使用的磁盘空间（阶段2，步骤2）
这样做的潜在缺点是磁盘碎片增加，以及由于向后读取分区而导致的性能损失。（在后一点上，在Linux/UNIX上向后读取文件需要更多的系统调用，而FS实现可能无法执行相反方向的“预读”。）
最后，我想指出，任何关于这个算法（以及其他算法）所用时间的理论预测，在很大程度上都是猜测。在真正的JVM+真正的OS+真正的光盘上，这些算法的行为太复杂，无法通过“返回信封”的计算给出可靠的答案。适当的处理需要实际的实施、调整和基准测试
# 5 楼答案
A1。您可能想要实现某种形式的合并排序
A2：比机器上有256GB内存的情况下更长
编辑：被批评刺痛，我引用维基百科关于合并排序的文章：
# 6 楼答案
听起来像是一个需要External sorting方法的任务。《计算机编程的艺术》第3卷包含一节，对外部排序方法进行了广泛讨论