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

排序在这里是次要问题。正如其他人所说，仅仅存储整数是困难的，并且不能在所有输入上工作，因为每个数字需要27位。

我对此的看法是:只存储连续(排序)整数之间的差异，因为它们很可能很小。然后使用压缩方案，例如，每个输入数字增加2位，来编码数字存储在多少位上。 喜欢的东西:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

在给定的内存限制内，应该能够存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学超出了我的范围。

我希望您能够利用输入的领域特定知识，在此基础上找到足够好的整数压缩方案。

哦，然后，当你收到数据时，你对那个排序的列表进行插入排序。

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

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

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

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

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

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

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

一般程序

所采取的方法如下。该算法在一个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字节来存储最终结果+开销。