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

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

伪代码思想:

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步。最后一步是，如果超出内存，则失败，或者在收集完所有数据后开始输出结果，即开始对范围进行排序，并按顺序输出结果，然后按需要解压缩的顺序解压结果，并在得到它们时对它们进行排序。

下面是这类问题的一般解决方案:

一般程序

所采取的方法如下。该算法在一个32位字的缓冲区上操作。它在循环中执行以下过程:

We start with a buffer filled with compressed data from the last iteration. The buffer looks like this |compressed sorted|empty| Calculate the maximum amount of numbers that can be stored in this buffer, both compressed and uncompressed. Split the buffer into these two sections, beginning with the space for compressed data, ending with the uncompressed data. The buffer looks like |compressed sorted|empty|empty| Fill the uncompressed section with numbers to be sorted. The buffer looks like |compressed sorted|empty|uncompressed unsorted| Sort the new numbers with an in-place sort. The buffer looks like |compressed sorted|empty|uncompressed sorted| Right-align any already compressed data from the previous iteration in the compressed section. At this point the buffer is partitioned |empty|compressed sorted|uncompressed sorted| Perform a streaming decompression-recompression on the compressed section, merging in the sorted data in the uncompressed section. The old compressed section is consumed as the new compressed section grows. The buffer looks like |compressed sorted|empty|

执行此过程，直到所有数字都已排序。

压缩

当然，这种算法只有在知道实际要压缩什么之前，才有可能计算出新排序缓冲区的最终压缩大小。其次，压缩算法需要足够好来解决实际问题。

所使用的方法使用三个步骤。首先，算法将始终存储排序序列，因此我们可以只存储连续条目之间的差异。每个差值都在[0,99999999]的范围内。

这些差异随后被编码为一元比特流。这个流中的1表示“向累加器添加1,0表示“将累加器作为一个条目发出，并重置”。所以差N由N个1和1个0表示。

所有差异的和将接近算法支持的最大值，所有差异的计数将接近算法中插入的值的数量。这意味着我们期望流在最后包含最大值1和计数0。这允许我们计算流中0和1的期望概率。即，0的概率为count/(count+maxval)， 1的概率为maxval/(count+maxval)。

我们使用这些概率来定义这个比特流上的算术编码模型。这个算术代码将在最佳空间中精确地编码1和0的数量。我们可以计算该模型对于任何中间位流所使用的空间:bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount)。若要计算算法所需的总空间，请将encoded设置为amount。

为了不需要大量的迭代，可以向缓冲区添加少量开销。这将确保算法将至少对适合这个开销的数量进行操作，因为到目前为止，算法最大的时间成本是每个周期的算术编码压缩和解压缩。

除此之外，在算术编码算法的定点近似中，存储簿记数据和处理轻微的不准确性是需要一些开销的，但总的来说，即使使用可以包含8000个数字的额外缓冲区，该算法也能够容纳1MiB的空间，总共1043916字节的空间。

最优

除了减少算法的开销外，理论上不可能得到更小的结果。为了仅仅包含最终结果的熵，1011717个字节是必要的。如果我们减去为提高效率而增加的额外缓冲区，该算法使用1011916字节来存储最终结果+开销。

如果数字的范围是有限的(只能有2个8位数，或者只有10个不同的8位数)，那么你可以编写一个优化的排序算法。但如果你想对所有可能的8位数进行排序，这在内存那么少的情况下是不可能的。

谷歌的(坏)方法，从HN线程。存储rle风格的计数。

你的初始数据结构是“99999999:0”(都是零，没有看到任何数字)，然后假设你看到了数字3,866,344，那么你的数据结构就变成了“3866343:0,1:1,96133654:0”，你可以看到数字总是在零位数和1位数之间交替，所以你可以假设奇数代表0位，偶数代表1位。这就变成了(3866343,1,96133654)

他们的问题似乎不包括副本，但让我们假设他们使用“0:1”来表示副本。

大问题#1:1M个整数的插入将花费很长时间。

大问题#2:像所有的普通增量编码解决方案一样，一些分布不能用这种方式覆盖。例如，1m整数，距离为0:99(例如，每个整数+99)。现在考虑相同的情况，但随机距离在0:99的范围内。(注:99999999/1000000 = 99.99)

谷歌的方法既不值得(缓慢)，也不正确。但要为他们辩护，他们的问题可能略有不同。

在10^8的范围内有10^6个值，所以平均每100个码点有一个值。存储第N个点到第(N+1)个点的距离。重复值的跳过值为0。这意味着跳跃平均需要7比特来存储，所以100万个跳跃将很适合我们的800万比特存储空间。

这些跳跃需要被编码成一个比特流，比如通过霍夫曼编码。插入是通过遍历比特流并在新值之后重写。通过遍历并写出隐含值来输出。出于实用性考虑，它可能被做成10^4个列表，每个列表包含10^4个代码点(平均100个值)。

随机数据的霍夫曼树可以通过假设跳跃长度上的泊松分布(均值=方差=100)先验地构建，但可以在输入上保留真实的统计数据，并用于生成处理病理病例的最佳树。

我们可以利用网络堆栈，在我们得到所有数字之前，按顺序发送数字。如果你发送1M的数据，TCP/IP会把它分解成1500字节的数据包，并按照目标发送。每个包将被赋予一个序列号。

我们可以用手来做。在填满内存之前，我们可以对现有的数据进行排序，并将列表发送给目标，但在每个数字周围的序列中留下空洞。然后用同样的方法处理第二个1/2的数字，使用序列中的这些洞。

远端的网络堆栈将按顺序组装结果数据流，然后将其提交给应用程序。

它使用网络来执行归并排序。这是一个完全的黑客，但我是受到之前列出的其他网络黑客的启发。