我在这里的建议很大程度上归功于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位增量的桶

诀窍是将算法状态表示为“增量计数器”=“+”和“输出计数器”=“!”字符的压缩流，这是一个整数多集。例如，集合{0,3,3,4}将被表示为“!+++!!+!”，后面跟着任意数量的“+”字符。要修改多集，您可以输出字符，每次只保持恒定的解压缩量，并在以压缩形式流回之前进行适当的更改。

细节

我们知道最终集合中恰好有10^6个数字，所以最多有10^6个“!”字符。我们还知道我们的范围大小为10^8，这意味着最多有10^8个“+”字符。10^6 "的排列方式!s在10^8 "+"s中的值是(10^8 + 10^6)选10^6，因此指定某种特定的排列需要大约0.965 MiB '的数据。那太紧了。

我们可以独立对待每个角色而不超出我们的配额。“+”字符正好是“!”字符的100倍，如果我们忘记了它们是相互依赖的，那么每个字符是“+”的概率就简化为100:1。100:101的几率对应于每个字符0.08位，对于几乎相同的~0.965 MiB(忽略依赖关系在这种情况下只有~12位的代价!)

The simplest technique for storing independent characters with known prior probability is Huffman coding. Note that we need an impractically large tree (A huffman tree for blocks of 10 characters has an average cost per block of about 2.4 bits, for a total of ~2.9 Mib. A huffman tree for blocks of 20 characters has an average cost per block of about 3 bits, which is a total of ~1.8 MiB. We're probably going to need a block of size on the order of a hundred, implying more nodes in our tree than all the computer equipment that has ever existed can store.). However, ROM is technically "free" according to the problem and practical solutions that take advantage of the regularity in the tree will look essentially the same.

伪代码

Have a sufficiently large huffman tree (or similar block-by-block compression data) stored in ROM Start with a compressed string of 10^8 "+" characters. To insert the number N, stream out the compressed string until N "+" characters have gone past then insert a "!". Stream the recompressed string back over the previous one as you go, keeping a constant amount of buffered blocks to avoid over/under-runs. Repeat one million times: [input, stream decompress>insert>compress], then decompress to output

由于ROM大小不计算，因此除了TCP缓冲区外，不需要任何额外的RAM。只需要实现一个大的有限状态机。每个状态表示读入的多组数字。在读取了一百万个数字之后，只需打印出与所达到的状态相对应的数字。

如果输入流可以接收几次，这将是很大的 更简单(没有关于这方面的信息，想法和时间-性能问题)。

然后，我们可以数小数。如果是计数值的话 容易使输出流。通过计算值来压缩。它 这取决于输入流中的内容。

在接收流时执行这些步骤。

首先设置一些合理的块大小

伪代码思想:

The first step would be to find all the duplicates and stick them in a dictionary with its count and remove them. The third step would be to place number that exist in sequence of their algorithmic steps and place them in counters special dictionaries with the first number and their step like n, n+1..., n+2, 2n, 2n+1, 2n+2... Begin to compress in chunks some reasonable ranges of number like every 1000 or ever 10000 the remaining numbers that appear less often to repeat. Uncompress that range if a number is found and add it to the range and leave it uncompressed for a while longer. Otherwise just add that number to a byte[chunkSize]

在接收流时继续执行前4步。最后一步是，如果超出内存，则失败，或者在收集完所有数据后开始输出结果，即开始对范围进行排序，并按顺序输出结果，然后按需要解压缩的顺序解压结果，并在得到它们时对它们进行排序。

我认为从组合学的角度来思考这个问题:有多少种可能的排序数字的组合?如果我们给出的组合是0,0,0 ....，0代码0，和0,0,0，…，1代码1，和999999999,99999999，…99999999是代码N, N是什么?换句话说，结果空间有多大?

Well, one way to think about this is noticing that this is a bijection of the problem of finding the number of monotonic paths in an N x M grid, where N = 1,000,000 and M = 100,000,000. In other words, if you have a grid that is 1,000,000 wide and 100,000,000 tall, how many shortest paths from the bottom left to the top right are there? Shortest paths of course require you only ever either move right or up (if you were to move down or left you would be undoing previously accomplished progress). To see how this is a bijection of our number sorting problem, observe the following:

您可以将路径中的任何水平支腿想象成排序中的一个数字，其中支腿的Y位置表示值。

所以如果路径只是向右移动一直到最后，然后一直跳到顶部，这相当于顺序为0,0,0，…，0。相反，如果它开始时一直跳到顶部，然后向右移动1,000,000次，这相当于999999999,99999999，……, 99999999。它向右移动一次，然后向上移动一次，然后向右移动一次，然后向上移动一次，等等，直到最后(然后必然会一直跳到顶部)，相当于0,1,2,3，…，999999。

幸运的是，这个问题已经解决了，这样的网格有(N + M)个选择(M)条路径:

(1,000,000 + 100,000,000)选择(100,000,000)~= 2.27 * 10^2436455

N因此等于2.27 * 10^2436455，因此代码0表示0,0,0，…，0和代码2.27 * 10^2436455，一些变化表示999999999,99999999，…, 99999999。

为了存储从0到2.27 * 10^2436455的所有数字，您需要lg2(2.27 * 10^2436455) = 8.0937 * 10^6位。

1兆字节= 8388608比特> 8093700比特

这样看来，我们至少有足够的空间来存储结果!当然，有趣的部分是在数字流进来时进行排序。不确定最好的方法是我们有294908位剩余。我想一个有趣的技巧是在每个点都假设这是整个排序，找到该排序的代码，然后当你收到一个新数字时，返回并更新之前的代码。手，手，手。