If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.

假设这个任务是可能的。在输出之前，内存中会有一个百万个排序数字的表示。有多少种不同的表示法?由于可能有重复的数字，我们不能使用nCr(选择)，但有一种叫做multichoose的操作，它适用于多集。

在0..99,999,999范围内有22e2436455种方法来选择一百万个数字。 这需要8,093,730位来表示每个可能的组合，或1,011,717字节。

所以理论上是可能的，如果你能想出一个合理(足够)的数字排序表。例如，一个疯狂的表示可能需要一个10MB的查找表或数千行代码。

但是，如果“1M RAM”意味着100万个字节，那么显然没有足够的空间。事实上，多5%的内存使它在理论上成为可能，这对我来说意味着表示必须非常有效，可能是不理智的。

If it is possible to read the input file more than once (your problem statement doesn't say it can't), the following should work. It is described in Benchley's book "Programming Perls." If we store each number in 8 bytes we can store 250,000 numbers in one megabyte. Use a program that makes 40 passes over the input file. On the first pass it reads into memory any integer between 0 and 249,999, sorts the (at most) 250,000 integers and writes them to the output file. The second pass sorts the integers from 250,000 to 499,999 and so on to the 40th pass, which sorts 9,750,000 to 9,999,999.

我在这里的建议很大程度上归功于Dan的解决方案

首先，我假设解决方案必须处理所有可能的输入列表。我认为流行的答案并没有做出这样的假设(在我看来这是一个巨大的错误)。

众所周知，任何形式的无损压缩都不会减小所有输入的大小。

所有流行的答案都假设它们能够有效地应用压缩来允许它们有额外的空间。事实上，一个足够大的额外空间块，以未压缩的形式保存他们部分完成的列表的一部分，并允许他们执行排序操作。这只是一个糟糕的假设。

对于这样的解决方案，任何了解如何进行压缩的人都能够设计一些不能很好地压缩该方案的输入数据，并且“解决方案”很可能会由于空间不足而崩溃。

相反，我采用数学方法。我们可能的输出是所有长度为LEN的列表，由0..MAX范围内的元素组成。这里LEN是1,000,000,MAX是100,000,000。

对于任意的LEN和MAX，编码此状态所需的比特数为:

Log2(MAX multichoice LEN)

因此，对于我们的数字，一旦我们完成了接收和排序，我们将需要至少Log2(100,000,000 MC 1,000,000)位来存储我们的结果，以一种能够唯一区分所有可能输出的方式。

这是~= 988kb。所以我们有足够的空间来存放结果。从这个角度来看，这是可能的。

[删除了无意义的漫谈，现在有更好的例子…]

最好的答案在这里。

另一个很好的答案是这里，它基本上使用插入排序作为函数，将列表扩展为一个元素(缓冲一些元素并进行预先排序，以允许一次插入多个元素，节省一些时间)。使用一个很好的压缩状态编码，7位增量的桶

你用的是哪种电脑?它可能没有任何其他“正常”的本地存储，但它是否有视频RAM，例如?100万像素x每像素32位(比如说)非常接近你所需的数据输入大小。

(我主要是问旧的Acorn RISC PC的内存，如果你选择低分辨率或低颜色深度的屏幕模式，它可以“借用”VRAM来扩展可用的系统RAM !)这在只有几MB普通RAM的机器上非常有用。

我想试试基数树。如果可以将数据存储在树中，那么就可以执行顺序遍历来传输数据。

我不确定你是否能把它装进1MB，但我认为值得一试。