我们有1 MB - 3 KB RAM = 2^23 - 3*2^13位= 8388608 - 24576 = 8364032位可用。

我们给出10^8范围内的10^6个数。这给出了~100 < 2^7 = 128的平均差距

让我们首先考虑一个比较简单的问题，即当所有间距都< 128时，数字间距相当均匀。这很简单。只存储第一个数字和7位空白:

(27位)+ 10^6个7位间隔数=需要7000027位

注意重复的数字间隔为0。

但如果间隔大于127呢?

好吧，让我们直接表示小于127的间隙大小，但是127的间隙大小后面跟着一个连续的8位编码来表示实际的间隙长度:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

etc.

注意这个数字表示描述了它自己的长度，所以我们知道下一个间隙数何时开始。

对于小于127的小间隙，仍然需要7000027位。

可能有高达(10^8)/(2^7)= 781250个23位的间隙数，需要额外的16* 781250 = 12500,000位，这是太多了。我们需要一个更紧凑和缓慢增加的差距表示。

平均差距大小是100，所以如果我们把它们重新排序 [100, 99, 101, 98, 102，…]， 2, 198, 1, 199, 0, 200, 201, 202，…] 然后用密集的二进制斐波那契基编码索引它，没有对零(例如，11011=8+5+2+1=16)，数字用“00”分隔，然后我认为我们可以保持足够短的差距表示，但它需要更多的分析。

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

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

你最多要数到99,999,999，并在沿途标明1,000,000个站点。因此，可以使用位流进行解释，即1表示递增计数器，0表示输出数字。如果流中的前8位是00110010，到目前为止我们将有0,0,2,2,3。

Log (99,999,999 + 1,000,000) / Log(2) = 26.59。你的内存中有2^28位。你只需要用一半!

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

我将利用TCP的重传行为。

让TCP组件创建一个大的接收窗口。 收到一定数量的包，但没有发送ACK。 处理这些传递，创建一些(前缀)压缩数据结构 对最后一个不再需要的数据包发送重复的ack /等待重传超时 转到2 所有数据包被接受

这假设了桶或多次传递的某种好处。

可能是通过对批次/桶进行排序并合并它们。->根树

使用这种技术接受并排序前80%，然后读取后20%，验证后20%不包含将落在最低数字的前20%的数字。然后发送最低的20%的数字，从内存中删除，接受剩下的20%的新数字并合并。**

If the numbers are evenly distributed we can use Counting sort. We should keep the number of times that each number is repeated in an array. Available space is: 1 MB - 3 KB = 1045504 B or 8364032 bits Number of bits per number= 8364032/1000000 = 8 Therefore, we can store the number of times each number is repeated to the maximum of 2^8-1=255. Using this approach we have an extra 364032 bits unused that can be used to handle cases where a number is repeated more than 255 times. For example we can say a number 255 indicates a repetition greater than or equal to 255. In this case we should store a sequence of numbers+repetitions. We can handle 7745 special cases as shown bellow:

364032/(表示每个数字所需的位数+表示100万所需的位数)= 364032 / (27+20)=7745