我有一台有1M内存的电脑，没有其他本地存储

另一种作弊方法:你可以使用非本地(网络)存储代替(你的问题不排除这一点)，调用一个网络服务，它可以使用直接的基于磁盘的归并排序(或者只需要足够的RAM来在内存中排序，因为你只需要接受1M的数字)，而不需要(公认非常巧妙的)已经给出的解决方案。

这可能是作弊，但不清楚你是在寻找一个现实问题的解决方案，还是一个让人扭曲规则的谜题……如果是后者，那么简单的欺骗可能比复杂但“真实”的解决方案(正如其他人指出的那样，后者只能用于可压缩输入)得到更好的结果。

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

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

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

你试过转换成十六进制吗?

我可以看到前后文件大小都有了很大的减小;然后，用自由空间分步计算。也许，再次转换为dec, order，十六进制，另一个块，转换为dec, order…

对不起. .我不知道是否可行

# for i in {1..10000};do echo $(od -N1 -An -i /dev/urandom) ; done > 10000numbers
# for i in $(cat 10000numbers ); do printf '%x\n' $i; done > 10000numbers_hex
# ls -lah total 100K
drwxr-xr-x  2 diego diego 4,0K oct 22 22:32 .
drwx------ 39 diego diego  12K oct 22 22:31 ..
-rw-r--r--  1 diego diego  29K oct 22 22:33 10000numbers_hex
-rw-r--r--  1 diego diego  35K oct 22 22:31 10000numbers

到目前为止，这里还没有提到一个相当狡猾的技巧。我们假设您没有额外的方法来存储数据，但严格来说这并不正确。

解决问题的一种方法是做以下可怕的事情，任何人在任何情况下都不应该尝试:使用网络流量存储数据。不，我指的不是NAS。

你可以用以下方法对只有几个字节内存的数字进行排序:

首先取两个变量:COUNTER和VALUE。 首先将所有寄存器设置为0; 每次你收到一个整数I，增加COUNTER并将VALUE设置为max(VALUE, I); 然后向路由器发送数据集为I的ICMP echo请求报文。擦掉I，重复。 每次收到返回的ICMP包时，只需提取整数并在另一个回显请求中再次发送出去。这将产生大量的ICMP请求，其中包含整数。

Once COUNTER reaches 1000000, you have all of the values stored in the incessant stream of ICMP requests, and VALUE now contains the maximum integer. Pick some threshold T >> 1000000. Set COUNTER to zero. Every time you receive an ICMP packet, increment COUNTER and send the contained integer I back out in another echo request, unless I=VALUE, in which case transmit it to the destination for the sorted integers. Once COUNTER=T, decrement VALUE by 1, reset COUNTER to zero and repeat. Once VALUE reaches zero you should have transmitted all integers in order from largest to smallest to the destination, and have only used about 47 bits of RAM for the two persistent variables (and whatever small amount you need for the temporary values).

我知道这很可怕，我知道可能会有各种各样的实际问题，但我想这可能会让你们中的一些人发笑，或者至少会吓到你们。

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

在所有可能的输入中，这个问题只有一个解决方案。作弊。

通过TCP读取m个值，其中m接近内存中可排序的最大值，可能是n/4。 对250,000(大约)个数字进行排序并输出。 重复做另外3个四分之三。 让接收方在处理时合并接收到的4个数字列表。(这并不比使用单个列表慢多少。)